## Rerooting A Binary Search Tree

### July 28, 2017

We’ve written about binary search trees on several occasions, most recently here. Binary search trees are a fruitful source of exercises, and we have another one today:

Write a program that takes a binary search tree and a given node of the tree and returns a new binary search tree with the given node at its root, changing as few nodes within the tree as necessary.

Your task is to write a program to reroot a binary search tree. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Here’s a solution in Java. It accumulates two lists of nodes with pre-order traversals, 1) for nodes not under the new root in the existing tree, and 2) for nodes under the new root (including the new root) in the existing tree. It then constructs the re-rooted tree by inserting nodes from list 2 then list 1.

The example reroots at node 5.

Output:

Here’s an alternative approach, which I prefer versus my earlier solution. I realized this when implementing Morris traversal for another programmingpraxis problem.

Here’s the algorithm. This re-roots in-place. For a non-destructive version, the tree could be copied prior to rerooting.

Here’s an implementation in Java.

Output: