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