## 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!

Pages: 1 2

### 2 Responses to “Rerooting A Binary Search Tree”

1. Daniel said

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;
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();
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<>();
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() {
}

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;
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
└── 2
```
2. Daniel said

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.

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

Here’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() {
}

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;
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
```