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 T₁ and T₂, such that every element in T₁ <= every element in T₂. 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 T₁ or left extreme node in T₂ to maintain BST property. So, the approach is to remove either of these nodes, make it as root, and attach T₁ as left subtree, T₂ as right subtree.