Print common nodes in two Binary Search Trees

By | April 17, 2016

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 1
             10
           /     \
           5      15
         /  \    /  \
        1   8   12   20

Tree 2

              7
           /     \
          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:-

  1. Do inorder traversal of tree 1.
  2. Store the data in an auxiliary array.
  3. Repeat the above two steps for tree 2.
  4. Find intersecting elements in both the arrays.
  5. 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:

  1. Traverse both trees using inorder traversal.
  2. Push the elements in an seperate stacks for each tree.
  3. 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)