Merge two Binary Search Tree with limited extra space

Problem:
Merge two Binary Search Tree with limited extra space
Given two Binary Search Trees(BST), print the elements of both BSTs in sorted form.
The expected time complexity is O(m+n) where m is the number of nodes in first tree and n is the number of nodes in second tree. Maximum allowed auxiliary space is O(height of the first tree + height of the second tree).

Solution
– Process tree1 in recursive InOrder
– Process tree2 in non recursive InOrder

Latest Source Code:
Github: MergeTwoBinarySearchTree.java


Output:

        20               
      / \       
     /   \      
    /     \     
   /       \    
   3       30       
  / \     / \   
 /   \   /   \  
 2   10   27   35   
        / \     
        26 28     
                                
       10               
      / \       
     /   \      
    /     \     
   /       \    
   7       30       
  / \     / \   
 /   \   /   \  
 5   8   25   50   
        / \     
        24 29     
                                
2 3 5 7 8 10 10 20 24 25 26 27 28 29 30 30 35 50 
Author: Hrishikesh Mishra