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