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.
Programming Praxis 
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.
import java.util.ArrayList; import java.util.Stack; public class BinarySearchTree<T extends Comparable<T>> { class Node { T value; Node left; Node right; Node(T value) { this.value = value; } } Node root; private Node insert(Node node, Node root) { if (root == null) return node; int compare = node.value.compareTo(root.value); if (compare < 0) { root.left = insert(node, root.left); } else { root.right = insert(node, root.right); } return root; } Node insert(T value) { Node node = new Node(value); root = insert(node, root); return node; } BinarySearchTree<T> reroot(Node newRoot) { // insert1 has nodes to insert first into rerooted BST ArrayList<Node> insert1 = new ArrayList<>(); // insert2 has nodes to insert second into rerooted BST ArrayList<Node> insert2 = new ArrayList<>(); // frontier tracks nodes for traversing the tree Stack<Node> frontier = new Stack<>(); frontier.push(root); while (!frontier.isEmpty()) { Node next = frontier.pop(); if (next == newRoot) continue; insert2.add(next); if (next.right != null) frontier.push(next.right); if (next.left != null) frontier.push(next.left); } frontier.push(newRoot); while (!frontier.isEmpty()) { Node next = frontier.pop(); insert1.add(next); if (next.right != null) frontier.push(next.right); if (next.left != null) frontier.push(next.left); } BinarySearchTree<T> bst = new BinarySearchTree<>(); ArrayList<Node> insert = new ArrayList<>(); insert.addAll(insert1); insert.addAll(insert2); for (Node node : insert) { bst.insert(node.value); } return bst; } public String toString(String prefix, Node node, boolean right) { if (node == null) return ""; StringBuffer sb = new StringBuffer(); sb.append(toString(prefix + (right ? " " : "│ "), node.right, true)); sb.append(prefix + (right ? "┌── " : "└── ") + node.value + "\n"); sb.append(toString(prefix + (right ? "│ " : " "), node.left, false)); return sb.toString(); } public String toString() { return toString("", root, false); } public static void main(String[] args) { BinarySearchTree<Integer> bst = new BinarySearchTree<>(); int[] values = {43,2,5,42,12,672,3,34}; BinarySearchTree.Node[] nodes = new BinarySearchTree.Node[values.length]; for (int i = 0; i < values.length; ++i) { nodes[i] = bst.insert(values[i]); } System.out.println("Original"); System.out.print(bst); BinarySearchTree.Node root = nodes[2]; BinarySearchTree<Integer> rerooted = bst.reroot(root); System.out.println(); System.out.println("Rerooted"); System.out.print(rerooted); } }Output:
Original │ ┌── 672 └── 43 │ ┌── 42 │ │ │ ┌── 34 │ │ └── 12 │ ┌── 5 │ │ └── 3 └── 2 Rerooted │ ┌── 672 │ ┌── 43 │ ┌── 42 │ │ │ ┌── 34 │ │ └── 12 └── 5 └── 3 └── 2Here’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.
While root != new_root: If new_root <= root: 1) Move root to the right child of its predecessor (predecessor is the rightmost node in root's left subtree). 2) Set root = root.left Else: 1) Move root to the left child of its successor (successor is the leftmost node in the root's right subtree). 2) Set root = root.rightHere’s an implementation in Java.
public class BinarySearchTree<T extends Comparable<T>> { class Node { T value; Node left; Node right; Node(T value) { this.value = value; } } Node root; private Node insert(Node node, Node root) { if (root == null) return node; int compare = node.value.compareTo(root.value); if (compare <= 0) { root.left = insert(node, root.left); } else { root.right = insert(node, root.right); } return root; } Node insert(T value) { Node node = new Node(value); root = insert(node, root); return node; } void reroot(Node newRoot) { while (root != newRoot) { Node oldRoot = root; int compare = newRoot.value.compareTo(oldRoot.value); if (compare <= 0) { Node predecessor = oldRoot.left; while (predecessor.right != null) { predecessor = predecessor.right; } predecessor.right = oldRoot; root = oldRoot.left; oldRoot.left = null; } else { Node successor = oldRoot.right; while (successor.left != null) { successor = successor.left; } root = oldRoot.right; oldRoot.right = null; successor.left = oldRoot; } } } public String toString(String prefix, Node node, boolean right) { if (node == null) return ""; StringBuffer sb = new StringBuffer(); sb.append(toString(prefix + (right ? " " : "│ "), node.right, true)); sb.append(prefix + (right ? "┌── " : "└── ") + node.value + "\n"); sb.append(toString(prefix + (right ? "│ " : " "), node.left, false)); return sb.toString(); } public String toString() { return toString("", root, false); } public static void main(String[] args) { BinarySearchTree<Integer> bst = new BinarySearchTree<>(); int[] values = {43,2,5,42,12,672,3,34}; BinarySearchTree.Node[] nodes = new BinarySearchTree.Node[values.length]; for (int i = 0; i < values.length; ++i) { nodes[i] = bst.insert(values[i]); } System.out.println("Original"); System.out.print(bst); BinarySearchTree.Node root = nodes[2]; bst.reroot(root); System.out.println(); System.out.println("Rerooted"); System.out.print(bst); } }Output:
Original │ ┌── 672 └── 43 │ ┌── 42 │ │ │ ┌── 34 │ │ └── 12 │ ┌── 5 │ │ └── 3 └── 2 Rerooted │ ┌── 672 │ ┌── 43 │ ┌── 42 │ │ │ ┌── 34 │ │ └── 12 └── 5 └── 3 └── 2