Rerooting A Binary Search Tree
July 28, 2017
I’ve been very busy at work, and didn’t have time to write a solution, so you’re on your own for this one. Have fun!
A collection of etudes, updated weekly, for the education and enjoyment of the savvy programmer
I’ve been very busy at work, and didn’t have time to write a solution, so you’re on your own for this one. Have fun!
Pages: 1 2
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: