Saturday, February 19, 2011
Combining (merge) two binary search trees
20th, February 2011
Given two binary search trees, how to combine them?
Note that the binary search tree has a property that every left subtree element will be less than or equal to the root element, and every right subtree element is greater than or equal to the root element.
Based on the property, let us assume that given trees T1 and T2, such that every element in T1 <= every element in T2. It will be easy to merge these two trees.
We need to figure out the root of merged tree. The root element can be either right extreme node in T1 or left extreme node in T2 to maintain BST property. So, the approach is to remove either of these nodes, make it as root, and attach T1 as left subtree, T2 as right subtree.