Merge two BSTs with constant extra space | C ++ implementation of above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; class Node { public : int data ; Node * left ; Node * right ; Node ( int x ) { data = x ; left = right = NULL ; } } ; void inorder ( Node * root ) { if ( root != NULL ) { inorder ( root -> left ) ; cout << root -> data << " ▁ " ; inorder ( root -> right ) ; } } void merge ( Node * root1 , Node * root2 ) { if ( ! root1 && ! root2 ) return ; if ( ! root1 ) { inorder ( root2 ) ; return ; } if ( ! root2 ) { inorder ( root1 ) ; return ; } Node * temp1 = root1 ; Node * prev1 = NULL ; while ( temp1 -> left ) { prev1 = temp1 ; temp1 = temp1 -> left ; } Node * temp2 = root2 ; Node * prev2 = NULL ; while ( temp2 -> left ) { prev2 = temp2 ; temp2 = temp2 -> left ; } if ( temp1 -> data <= temp2 -> data ) { cout << temp1 -> data << " ▁ " ; if ( prev1 == NULL ) { merge ( root1 -> right , root2 ) ; } else { prev1 -> left = temp1 -> right ; merge ( root1 , root2 ) ; } } else { cout << temp2 -> data << " ▁ " ; if ( prev2 == NULL ) { merge ( root1 , root2 -> right ) ; } else { prev2 -> left = temp2 -> right ; merge ( root1 , root2 ) ; } } } int main ( ) { Node * 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 ) ; return 0 ; }