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

$\endgroup$

2 Answers 2

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$

$\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, 2023 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, 2023 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.

$\endgroup$

Your Answer

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

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