# Print common nodes in two Binary Search Trees

### Problem statement to print common nodes in two Binary Search Trees (BST).

Given two binary search trees, print all the elements that are common in both the trees.

### Example:

INPUT:Tree 110 / \ 5 15 / \ / \ 1 8 12 20Tree 27 / \ 3 10 / \ / \ 2 5 8 11

OUTPUT:Common nodes -> 5,8,10

### Solution to Print common nodes in two Binary Search Trees:

Consider two binary search trees with the first tree having n nodes and the second with m nodes. We need to print the common nodes in both these trees.

### Method 1: Linear time solution using inorder traversal:-

- Do inorder traversal of tree 1.
- Store the data in an auxiliary array.
- Repeat the above two steps for tree 2.
- Find intersecting elements in both the arrays.
- Print the result.

### Algorithm for printing common nodes from inorder traversal:

#include <bits/stdc++.h> using namespace std; /*Structure of each node in the tree*/ struct node { int data; node *left; node *right; }; /*This function is used to create and initialise new nodes*/ node *newNode(int key) { node *temp = new node; temp->left = NULL; temp->right = NULL; temp->data = key; return temp; } /*This funciton is used to Insert new values in BST*/ node *Insert(node *root,int key) { if(!root) return newNode(key); if(key<root->data) root->left = Insert(root->left,key); else root->right = Insert(root->right,key); return root; } /*This function is used to print Inorder traversal*/ void Inorder(node *root,int arr1[]) { if(!root) return; Inorder(root->left,arr1); cout<<root->data<<" "; Inorder(root->right,arr1); } void createArray(node *root, int inorder[], int *ptr) { if(root == NULL) return; /*recur on left subchild*/ createArray(root->left, inorder, ptr ); inorder[*ptr] = root->data; (*ptr)++; /*recur on right subchild*/ createArray(root->right, inorder, ptr); } /*Function to print common noodes*/ int printCommon(int arr1[], int arr2[], int m, int n) { int i = 0, j = 0; while (i < m && j < n) { if (arr1[i] < arr2[j]) i++; else if (arr2[j] < arr1[i]) j++; /* if arr1[i] == arr2[j] */ else { printf("%d ", arr2[j++]); i++; } } } /* The function to create arrays from two BSTs */ void commonElements( node *root1, node *root2 ,int m,int n) { int *arr1 = new int[m]; int i = 0; createArray(root1,arr1,&i); int *arr2 = new int [n]; int j = 0; createArray(root2,arr2,&j); printCommon(arr1, arr2, m, n); return; } int main() { /* Let us create first BST 3 / \ 1 6*/ node *root1 = NULL; root1 = Insert(root1,3); Insert(root1, 1); Insert(root1, 6); /* Let us create second BST 3 / \ 1 5*/ node *root2 = NULL; root2 = Insert(root2, 3); Insert(root2, 1); Insert(root2, 5); commonElements(root1, root2,3 ,3); return 0; }

### Output:

1 3

### Time Complexity:O(n)

Extra Space:O(m+n)

## Method 2: Limited extra space using iterative inorder traversal

Total space required in this method is O(h1+h2) where h1 is the height of first tree and h2 of the second tree.

### Algorithm for printing common nodes from iterative inorder traversal:

- Traverse both trees using inorder traversal.
- Push the elements in an seperate stacks for each tree.
- Whenever same element is encountered in the traversal, print it.

### Solution code in C++ to build Binary Search Tree from sorted linked list:

#include <bits/stdc++.h> using namespace std; /*Structure of each node in the tree*/ struct node { int data; node *left; node *right; }; /*This function is used to create and initialise new nodes*/ node *newNode(int key) { node *temp=new node; temp->left=NULL; temp->right=NULL; temp->data=key; return temp; } /*This funciton is used to Insert new values in BST*/ node *Insert(node *root,int key) { if(!root) return newNode(key); if(key<root->data) root->left=Insert(root->left,key); else root->right=Insert(root->right,key); return root; } /*This function is used to print Inorder traversal*/ void Inorder(node *root) { if(!root) return; Inorder(root->left); cout<<root->data<<" "; Inorder(root->right); } /* The function to print common data of two BSTs*/ void commonElements( node *root1, node *root2) { /* s1 and s2 are stacks to hold elements of first and second BST respectively*/ stack<node *> s1,s2; while(1) { /* Push nodes of first BST*/ if(root1) { s1.push(root1); root1 = root1->left; } /* Push nodes of second BST*/ else if(root2) { s2.push(root2); root2 = root2->left; } else if(!s1.empty() && !s2.empty()) { root1 = s1.top(); root2 = s2.top(); if(root1->data == root2->data) { cout<<root1->data<<" "; s1.pop(); s2.pop(); /*increment both the roots*/ root1 = root1->right; root2 = root2->left; } else if(s1.top() < s2.top()) { s1.pop(); root1 = root1->right; /*root2 iis set to NULL becuse we traverse s1 till its elements are smaller*/ root2 = NULL; } else { s2.pop(); root2 = root2->right; /*root1 iis set to NULL becuse we traverse s2 till its elements are smaller*/ root1 = NULL; } } else break; } } int main() { /* Let us create first BST 3 / \ 1 6*/ node *root1 = NULL; root1 = Insert(root1,3); Insert(root1, 1); Insert(root1, 6); /* Let us create second BST 3 / \ 2 5*/ node *root2 = NULL; root2 = Insert(root2, 3); Insert(root2, 1); Insert(root2, 5); commonElements(root1, root2); return 0; }

### Output:

1 3

### Time Complexity: **O(n)**

Extra Space: O(log m + log n)

Extra Space: O(log m + log n)