Print Common Nodes in Two Binary Search Trees | Java 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
import java . util . * ; class GfG { static class Node { int key ; Node left , right ; } static Node newNode ( int ele ) { Node temp = new Node ( ) ; temp . key = ele ; temp . left = null ; temp . right = null ; return temp ; } static void printCommon ( Node root1 , Node root2 ) { Stack < Node > s1 = new Stack < Node > ( ) ; Stack < Node > s2 = new Stack < Node > ( ) ; while ( true ) { if ( root1 != null ) { s1 . push ( root1 ) ; root1 = root1 . left ; } else if ( root2 != null ) { s2 . push ( root2 ) ; root2 = root2 . left ; } else if ( ! s1 . isEmpty ( ) && ! s2 . isEmpty ( ) ) { root1 = s1 . peek ( ) ; root2 = s2 . peek ( ) ; if ( root1 . key == root2 . key ) { System . out . print ( 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 ; } } static void inorder ( Node root ) { if ( root != null ) { inorder ( root . left ) ; System . out . print ( root . key + " ▁ " ) ; inorder ( root . right ) ; } } static Node insert ( 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 ; } public static void main ( String [ ] args ) { 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 ) ; System . out . print ( " Tree ▁ 1 ▁ : ▁ " + "NEW_LINE");  inorder ( root1 ) ; System . out . println ( ) ; System . out . print ( " Tree ▁ 2 ▁ : ▁ " + "NEW_LINE");  inorder ( root2 ) ; System . out . println ( ) ; System . out . println ( " Common ▁ Nodes : ▁ " ) ; printCommon ( root1 , root2 ) ; } }