Print Common Nodes in Two Binary Search Trees | C ++ program of iterative traversal based method to find common elements in two BSTs . ; A BST node ; A utility function to create a new node ; Function two print common elements in given two trees ; Create two stacks for two inorder traversals ; push the Nodes of first tree in stack s1 ; push the Nodes of second tree in stack s2 ; Both root1 and root2 are NULL here ; If current keys in two trees are same ; move to the inorder successor ; If Node of first tree is smaller , than that of second tree , then its obvious that the inorder successors of current Node can have same value as that of the second tree Node . Thus , we pop from s2 ; root2 is set to NULL , because we need new Nodes of tree 1 ; Both roots and both stacks are empty ; A utility function to do inorder traversal ; A utility function to insert a new Node with given key in BST ; If the tree is empty , return a new Node ; Otherwise , recur down the tree ; return the ( unchanged ) Node pointer ; Driver program ; Create first tree as shown in example ; Create second tree as shown in example
#include <iostream> NEW_LINE #include <stack> NEW_LINE using namespace std ; struct Node { int key ; struct Node * left , * right ; } ; Node * newNode ( int ele ) { Node * temp = new Node ; temp -> key = ele ; temp -> left = temp -> right = NULL ; return temp ; } void printCommon ( Node * root1 , Node * root2 ) { stack < Node * > stack1 , s1 , s2 ; while ( 1 ) { if ( root1 ) { s1 . push ( root1 ) ; root1 = root1 -> left ; } else if ( root2 ) { s2 . push ( root2 ) ; root2 = root2 -> left ; } else if ( ! s1 . empty ( ) && ! s2 . empty ( ) ) { root1 = s1 . top ( ) ; root2 = s2 . top ( ) ; if ( root1 -> key == root2 -> key ) { cout << root1 -> key << " ▁ " ; s1 . pop ( ) ; s2 . pop ( ) ; root1 = root1 -> right ; root2 = root2 -> right ; } else if ( root1 -> key < root2 -> key ) { s1 . pop ( ) ; root1 = root1 -> right ; root2 = NULL ; } else if ( root1 -> key > root2 -> key ) { s2 . pop ( ) ; root2 = root2 -> right ; root1 = NULL ; } } else break ; } } void inorder ( struct Node * root ) { if ( root ) { inorder ( root -> left ) ; cout << root -> key << " ▁ " ; inorder ( root -> right ) ; } } struct Node * insert ( struct Node * node , int key ) { if ( node == NULL ) return newNode ( key ) ; if ( key < node -> key ) node -> left = insert ( node -> left , key ) ; else if ( key > node -> key ) node -> right = insert ( node -> right , key ) ; return node ; } int main ( ) { Node * root1 = NULL ; root1 = insert ( root1 , 5 ) ; root1 = insert ( root1 , 1 ) ; root1 = insert ( root1 , 10 ) ; root1 = insert ( root1 , 0 ) ; root1 = insert ( root1 , 4 ) ; root1 = insert ( root1 , 7 ) ; root1 = insert ( root1 , 9 ) ; Node * root2 = NULL ; root2 = insert ( root2 , 10 ) ; root2 = insert ( root2 , 7 ) ; root2 = insert ( root2 , 20 ) ; root2 = insert ( root2 , 4 ) ; root2 = insert ( root2 , 9 ) ; cout << " Tree ▁ 1 ▁ : ▁ " ; inorder ( root1 ) ; cout << endl ; cout << " Tree ▁ 2 ▁ : ▁ " ; inorder ( root2 ) ; cout << " Common Nodes : " printCommon ( root1 , root2 ) ; return 0 ; }