#codingexercise 

Merge two BSTs 

One method to do this is to use two auxiliary stacks for two BSTs.  If we get a element smaller from the trees, we print it. If the element is greater, we push it to the stack for the next iteration. 

We use the iterative inorder traversal :  

• Create an empty stack S 

• Initialize current node as root 

• Push the current node to stack S, set current to current.left, until current is NULL 

• If the current is null and stack is not empty then 

• Pop the top item from stack 

• Print the popped item 

• Set current = popped_item.right 

• Goto step 3 

• If current is null and the stack is empty, then we are done. 

To merge the BST we do the following: 

Initialize two stacks s1 and s2 from null. 

If the first tree is null, do iterative inorder traversal of second to print the merge 

If the second tree is null, do iterative inorder traversal of first to print the merge 

Set current in tree 1 to be cur1 and current in tree 2 to be cur2 

While either cur1 or cur 2 is not null or  one of the stacks is not empty: 

• If cur 1 or cur 2 is not null 

• For both the tree, if the current is not null, push it onto the stack, set current to current.left This will be repeated by the while until current is nul is null 

• Else 

• If either of the stacks is empty, then one tree is exhausted, print the other tree.  Do this for both stacks. 

• Set the current of each tree to the popped element from respective tree 

• Compare the two current and execute an iteration of step3 from iterative inorder traversal above  - the smaller of the two current nodes is printed, the larger pushed back on its corresponding stack 

At the end of the while loop, both stacks should be empty and the currents must be pointing to null and both the trees would be printed. 

#CODINGEXERCISE: CodingExercise-02-09-2025.docx