Introduction

A common interpretation of this problem is: given a permutation, build the binary search tree that would result from inserting the permutation values in order. The naive algorithm inserts one value at a time and can degrade to quadratic time, but you can reconstruct the same tree in O(n log n) by using ordered lookup for predecessors and successors.

Why the Naive Approach Can Be Too Slow

If you insert each value into a plain binary search tree one by one, a bad permutation such as sorted input creates a chain:

11
2 \
3  2
4   \
5    3

That means each insertion can take linear time, so the total work can become O(n^2).

To hit O(n log n), you need a faster way to find where each new node belongs.

Key Observation: Parent Comes from Neighbors Already Seen

Process the permutation from left to right. When you add a new value x, among the values already inserted:

• let pred be the greatest value smaller than x
• let succ be the smallest value greater than x

The parent of x in the BST is one of those two neighbors. The correct one is the neighbor that was inserted later, because that node sits lower in the partial tree and is the one that would receive x during normal insertion.

That reduces the problem to:

1. keep inserted values in sorted order
2. find predecessor and successor quickly
3. attach the new node to the later-created neighbor

A Runnable Python Implementation

The code below uses bisect to maintain a sorted list of inserted keys. The list operations are not ideal for very large n, but the reconstruction logic is the important part and is easy to verify. In languages with balanced trees such as std::set in C++ or TreeSet in Java, the same idea reaches true O(n log n).

1from bisect import bisect_left, insort
2
3
4class Node:
5    def __init__(self, value):
6        self.value = value
7        self.left = None
8        self.right = None
9
10
11def build_bst_from_permutation(perm):
12    if not perm:
13        return None
14
15    nodes = {}
16    inserted_at = {}
17    sorted_values = []
18
19    root = Node(perm[0])
20    nodes[perm[0]] = root
21    inserted_at[perm[0]] = 0
22    sorted_values.append(perm[0])
23
24    for t, x in enumerate(perm[1:], start=1):
25        node = Node(x)
26        nodes[x] = node
27        inserted_at[x] = t
28
29        i = bisect_left(sorted_values, x)
30        pred = sorted_values[i - 1] if i > 0 else None
31        succ = sorted_values[i] if i < len(sorted_values) else None
32
33        if pred is None:
34            parent_value = succ
35        elif succ is None:
36            parent_value = pred
37        else:
38            parent_value = pred if inserted_at[pred] > inserted_at[succ] else succ
39
40        parent = nodes[parent_value]
41        if x < parent.value:
42            parent.left = node
43        else:
44            parent.right = node
45
46        insort(sorted_values, x)
47
48    return root
49
50
51def preorder(node):
52    if not node:
53        return []
54    return [node.value] + preorder(node.left) + preorder(node.right)
55
56
57tree = build_bst_from_permutation([3, 1, 4, 2, 5])
58print(preorder(tree))

The resulting structure is the same as repeated BST insertion, but the parent decision is driven by ordered neighbors instead of a full tree walk from the root each time.

Why the Neighbor Rule Works

In a BST built from insertion order, the position of a new key is constrained by the closest smaller and closest larger keys already present. One of those two keys becomes the first node that can legally accept the new value as a child. The later-inserted one is deeper and therefore closer to the eventual insertion point.

That is the reason predecessor and successor carry enough information.

A Note on Stronger Results

There are specialized linear-time constructions for related tree problems, especially Cartesian trees. But for the BST-from-permutation interpretation, the ordered-neighbor method gives a solid O(n log n) approach and is much better than naive repeated insertion in the worst case.

Common Pitfalls

The biggest pitfall is assuming repeated BST insertion is automatically O(n log n). That is only true for balanced trees or favorable input orders.

Another issue is choosing the wrong parent when both predecessor and successor exist. The deciding rule is not smaller versus larger. It is which neighbor was inserted later.

People also confuse this problem with constructing a balanced BST from sorted values. A permutation-defined BST preserves insertion-order structure, which is a different goal.

Summary

• A natural interpretation is reconstructing the BST produced by inserting the permutation in order.
• Naive repeated insertion can take O(n^2) in the worst case.
• An O(n log n) solution uses predecessor and successor among already inserted keys.
• The parent of a new value is the later-inserted one of those two neighbors.
• This reconstructs the same BST shape without a full root-to-leaf insertion walk every time.