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 Tand 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 Tor 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 Tas left subtree, Tas right subtree.

1 comment:

Anonymous said...

Please Visit the blog
dailybrainteaser.blogspot.com