Construct a binary tree from permutation in n log n time

Question

The numbers 1 to n are inserted in a binary search tree in a specified order p_1, p_2,..., p_n. Describe an O(nlog n) time algorithm to construct the resulting final binary search tree.

Note that :-

1. I don't need average time n log n, but the worst time.
2. I need the the exact tree that results when insertion takes place with the usual rules. AVL or red black trees not allowed.

This is an assignment question. It is very very non trivial. In fact it seemed impossible at first glance. I have thought on it much. My observations:-

1. The argument that we use to prove that sorting takes atleast n log n time does not eliminate the existence of such an algorithm here.
2. If it is always possible to find a subtree in O(n) time whose size is between two fractions of the size of tree, the problem can be easily solved.
3. Choosing median or left child of root as root of subtree doesn't work.

Answer 1

Here's a linear-time algorithm. (I said that I wasn't going to work on this question, so if you like this answer, please award the bounty to SergGr.)

Create a doubly linked list with nodes 1..n and compute the inverse of p. For i from n down to 1, let q be the left neighbor of p_i in the list, and let r be the right neighbor. If p^-1(q) > p^-1(r), then make p_i the right child of q. If p^-1(q) < p^-1(r), then make p_i the left child of r. Delete p_i from the list.

In Python:

class Node(object):
    __slots__ = ('left', 'key', 'right')

    def __init__(self, key):
        self.left = None
        self.key = key
        self.right = None


def construct(p):
    # Validate the input.
    p = list(p)
    n = len(p)
    assert set(p) == set(range(n))  # 0 .. n-1

    # Compute p^-1.
    p_inv = [None] * n
    for i in range(n):
        p_inv[p[i]] = i

    # Set up the list.
    nodes = [Node(i) for i in range(n)]
    for i in range(n):
        if i >= 1:
            nodes[i].left = nodes[i - 1]
        if i < n - 1:
            nodes[i].right = nodes[i + 1]

    # Process p.
    for i in range(n - 1, 0, -1):  # n-1, n-2 .. 1
        q = nodes[p[i]].left
        r = nodes[p[i]].right
        if r is None or (q is not None and p_inv[q.key] > p_inv[r.key]):
            print(p[i], 'is the right child of', q.key)
        else:
            print(p[i], 'is the left child of', r.key)
        if q is not None:
            q.right = r
        if r is not None:
            r.left = q


construct([1, 3, 2, 0])

Answer 2

As David Eisenstat doesn't have time to extend his answer, I'll try to put more details into a similar algorithm.

Intuition

The main intuition behind the algorithm is based on the following statements:

statement #1: if a BST contains values a and b (a < b) AND there are no values between them, then either A (node for value a) is a (possibly indirect) parent of B (node for value b) or B is a (possibly indirect) parent of A.

This statement is obviously true because if their lowest common ancestor C is some other node than A and B, its value c must be between a and b. Note that statement #1 is true for any BST (balanced or unbalanced).

statement #2: if a simple (unbalanced) BST contains values a and b (a < b) AND there are no values between them AND we are trying to add value x such that a < x < b, then X (node for value x) will be either direct right (greater) child of A or direct left (less) child of B whichever node is lower in the tree.

Let's assume that the lower of two nodes is a (the other case is symmetrical). During insertion phase value x will travel the same path as a during its insertion because tree doesn't contain any values between a and x i.e. at any comparison values a and x are indistinguishable. It means that value x will navigate tree till node A and will pass node B at some earlier step (see statement #1). As x > a it should become a right child of A. Direct right child of A must be empty at this point because A is in B's subtree i.e. all values in that subtree are less than b and since there are no values between a and b in the tree, no value can be right child of node A.

Note that statement #2 might potentially be not true for some balanced BST after re-balancing was performed although this should be a strange case.

statement #3: in a balanced BST for any value x not in the tree yet, you can find closest greater and closest less values in O(log(N)) time.

This follows directly from statements #1 and #2: all you need is find the potential insertion point for the value x in the BST (takes O(log(N))), one of the two values will be direct parent of the insertion point and to find the other you need to travel the tree back to the root (again takes O(log(N))).

So now the idea behind the algorithm becomes clear: for fast insertion into an unbalanced BST we need to find nodes with closest less and greater values. We can easily do it if we additionally maintain a balanced BST with the same keys as our target (unbalanced) BST and with corresponding nodes from that BST as values. Using that additional data structure we can find insertion point for each new value in O(log(N)) time and update this data structure with new value in O(log(N)) time as well.

Algorithm

1. Init "main" root and balancedRoot with null.
2. for each value x in the list do:
3. if this is the first value just add it as the root nodes to both trees and go to #2
4. in the tree specified by balancedRoot find nodes that correspond to the closest less (BalancedA, points to node A in the main BST) and closest greater (BalancedB, points to node B in the main BST) values.
5. • If there is no closest lower value i.e. we are adding minimum element, add it as the left child to the node B
   • If there is no closest greater value i.e. we are adding maximum element, add it as the right child to the node A
   • Find whichever of nodes A or B is lower in the tree. You can use explicit level stored in the node. If the lower node is A (less node), add x as the direct right child of A else add x as the direct left child of B (greater node). Alternatively (and more cleverly) you may notice that from the statements #1 and #2 follows that exactly one of the two candidate insert positions (A's right child or B's left child) will be empty and this is where you want to insert your value x.

6. Add value x to the balanced tree (might re-use from step #4).

7. Go to step #2

As no inner step of the loop takes more than O(log(N)), total complexity is O(N*log(N))

Java implementation

I'm too lazy to implement balanced BST myself so I used standard Java TreeMap that implements Red-Black tree and has useful lowerEntry and higherEntry methods that correspond to step #4 of the algorithm (you may look at the source code to ensure that both are actually O(log(N))).

import java.util.Map;
import java.util.TreeMap;

public class BSTTest {

    static class Node {
        public final int value;
        public Node left;
        public Node right;

        public Node(int value) {
            this.value = value;
        }

        public boolean compareTree(Node other) {
            return compareTrees(this, other);
        }

        public static boolean compareTrees(Node n1, Node n2) {

            if ((n1 == null) && (n2 == null))
                return true;
            if ((n1 == null) || (n2 == null))
                return false;
            if (n1.value != n2.value)
                return false;
            return compareTrees(n1.left, n2.left) &&
                    compareTrees(n1.right, n2.right);
        }


        public void assignLeftSafe(Node child) {
            if (this.left != null)
                throw new IllegalStateException("left child is already set");
            this.left = child;
        }

        public void assignRightSafe(Node child) {
            if (this.right != null)
                throw new IllegalStateException("right child is already set");
            this.right = child;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    '}';
        }
    }


    static Node insertToBst(Node root, int value) {
        if (root == null)
            root = new Node(value);
        else if (value < root.value)
            root.left = insertToBst(root.left, value);
        else  
            root.right = insertToBst(root.right, value);
        return root;
    }


    static Node buildBstDirect(int[] values) {
        Node root = null;
        for (int v : values) {
            root = insertToBst(root, v);
        }
        return root;
    }

    static Node buildBstSmart(int[] values) {
        Node root = null;
        TreeMap<Integer, Node> balancedTree = new TreeMap<Integer, Node>();
        for (int v : values) {
            Node node = new Node(v);
            if (balancedTree.isEmpty()) {
                root = node;
            } else {
                Map.Entry<Integer, Node> lowerEntry = balancedTree.lowerEntry(v);
                Map.Entry<Integer, Node> higherEntry = balancedTree.higherEntry(v);
                if (lowerEntry == null) {
                    // adding minimum value
                    higherEntry.getValue().assignLeftSafe(node);
                } else if (higherEntry == null) {
                    // adding max value
                    lowerEntry.getValue().assignRightSafe(node);
                } else {
                    // adding some middle value
                    Node lowerNode = lowerEntry.getValue();
                    Node higherNode = higherEntry.getValue();
                    if (lowerNode.right == null)
                        lowerNode.assignRightSafe(node);
                    else
                        higherNode.assignLeftSafe(node);
                }
            }
            // update balancedTree
            balancedTree.put(v, node);
        }
        return root;
    }

    public static void main(String[] args) {
        int[] input = new int[]{7, 6, 9, 4, 1, 8, 2, 5, 3};

        Node directRoot = buildBstDirect(input);
        Node smartRoot = buildBstSmart(input);
        System.out.println(directRoot.compareTree(smartRoot));
    }
}