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.
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