Merge two BSTs with constant extra space | Structure of a BST Node ; A utility function to print Inorder traversal of a Binary Tree ; The function to print data of two BSTs in sorted order ; Base cases ; If the first tree is exhausted simply print the inorder traversal of the second tree ; If second tree is exhausted simply print the inoreder traversal of the first tree ; A temporary pointer currently pointing to root of first tree ; previous pointer to store the parent of temporary pointer ; Traverse through the first tree until you reach the leftmost element , which is the first element of the tree in the inorder traversal . This is the least element of the tree ; Another temporary pointer currently pointing to root of second tree ; Previous pointer to store the parent of second temporary pointer ; Traverse through the second tree until you reach the leftmost element , which is the first element of the tree in inorder traversal . This is the least element of the tree . ; Compare the least current least elements of both the tree ; If first tree 's element is  smaller print it ; If the node has no parent , that means this node is the root ; Simply make the right child of the root as new root ; If node has a parent ; As this node is the leftmost node , it is certain that it will not have a let child so we simply assign this node ' s ▁ right ▁ pointer , ▁ which ▁ can ▁ be ▁ ▁ either ▁ null ▁ or ▁ not , ▁ to ▁ its ▁ parent ' s left pointer . This statement is just doing the task of deleting the node ; recursively call the merge function with updated tree ; If the node has no parent , that means this node is the root ; Simply make the right child of root as new root ; If node has a parent ; Recursively call the merge function with updated tree ; Driver Code ; Print sorted nodes of both trees
class Node { constructor ( num ) { this . data = num ; this . left = this . right = null ; } } function inorder ( root ) { if ( root != null ) { inorder ( root . left ) ; document . write ( root . data + " " ) ; inorder ( root . right ) ; } } function merge ( root1 , root2 ) { if ( root1 == null && root2 == null ) return ; if ( root1 == null ) { inorder ( root2 ) ; return ; } if ( root2 == null ) { inorder ( root1 ) ; return ; } let temp1 = root1 ; let prev1 = null ; while ( temp1 . left != null ) { prev1 = temp1 ; temp1 = temp1 . left ; } let temp2 = root2 ; let prev2 = null ; while ( temp2 . left != null ) { prev2 = temp2 ; temp2 = temp2 . left ; } if ( temp1 . data <= temp2 . data ) { document . write ( temp1 . data + " " ) ; if ( prev1 == null ) { merge ( root1 . right , root2 ) ; } else { prev1 . left = temp1 . right ; merge ( root1 , root2 ) ; } } else { document . write ( temp2 . data + " " ) ; if ( prev2 == null ) { merge ( root1 , root2 . right ) ; } else { prev2 . left = temp2 . right ; merge ( root1 , root2 ) ; } } } let root1 = null , root2 = null ; root1 = new Node ( 3 ) ; root1 . left = new Node ( 1 ) ; root1 . right = new Node ( 5 ) ; root2 = new Node ( 4 ) ; root2 . left = new Node ( 2 ) ; root2 . right = new Node ( 6 ) ; merge ( root1 , root2 ) ;