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!

Advertisements

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: