1
$\begingroup$

Consider two binary search trees T1 and T2, each with height h, with all values in T1 less than all values in T2. I want to merge these both trees to get a new binary search tree of height at most h+1

My Thoughts:
The first thought was to put T1 as the left child of the leftmost node in T2. But the resulting bst will have height > h+1 I am not sure if there is a clever way to achieve this

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

Take the smallest element from $T_2$ (it will be the left-most leaf) and call it $r$. Note that you may have to "fix" $r$'s right child by putting it in place of where $r$ was.

Make the new tree such that $r$ is the root, $T_1$ is the left-child of $r$ and $T_2$ (with $r$ removed) is the right-child of $r$

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks that makes sense. What if we wanted to merge two red-black trees? Will similar approach work? $\endgroup$
    – nicku
    Mar 4 at 11:53
  • $\begingroup$ Not as-is, because if $r$ is black, its parent is red and also it has a red right child - you can't just simply remove $r$ since it would create a red child of a red node. $\endgroup$
    – nir shahar
    Mar 4 at 12:24
1
$\begingroup$

Either the rightmost node of the left tree or the leftmost node of the right tree can be used as a common root.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.