DSA sheet · Trees · Binary Search Tree pattern

BST from Preorder

In the binary tree section we rebuilt a tree from two traversals (preorder + inorder, and so on). A plain binary tree needs two. A BST needs only one, because the BST rule tells us where every value must go. The teacher solves it twice: first a brute force that searches for the "split point" at every node (O(n²)), then an optimal one that carries an upper bound down the recursion and builds the tree in a single pass (O(n)).

The upper-bound trick is worth learning well. It's the same "allowed range" thinking as Validate BST, but used to build a tree instead of checking one.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the conditions from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Brute force: find the split point
• Part B · Optimal: one pass with an upper bound
• Part C · Revision page

Part 0 · Before starting

What is a tree node?

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

The BST property

In a Binary Search Tree, for every node: every value in its left subtree (the left child and everything below it) is smaller than the node, and every value in its right subtree is bigger. It's about all nodes below, not just the children.

      8
     / \
    5   10
   / \
  1   7

      8
     / \
    5   10
   / \
  1   9

9 is bigger than its parent 5, so as a right child of 5 it looks fine. But it's in the left subtree of 8, and 9 > 8. That breaks the rule.

A side fact you'll see often: an inorder walk (left → node → right) of a BST gives the values in sorted order. At each node it lists all smaller values, then the node, then all bigger ones. This problem doesn't need it, but it explains why one traversal is enough: the inorder of a BST is always just its values sorted.

Preorder traversal

Preorder visits node → left subtree → right subtree, doing the same thing inside each subtree. For the BST above (with 12 as 10's right child, see Example 1 below) preorder gives 8 5 1 7 10 12.

• The first value is always the root, since the node comes before its children.
• After the root comes the whole left subtree in one block, and then the whole right subtree in one block.
• In a BST, the left block holds only values smaller than the root and the right block only values bigger. So the left block is exactly the run of values smaller than the root that comes right after it.

preorder:  [ 8 | 5  1  7 | 10  12 ]
            root  left (<8)  right (>8)

Part A · Brute force: find the split point

LeetCode 1008

1The question in simple words

You get a list preorder, which is the preorder traversal of some BST. You aren't given the tree. Build that BST and return its root.

        8
       / \
      5   10
     / \    \
    1   7    12

    1
     \
      3

2What the constraints tell us

• Length: 1 to 100. Very small. Even O(n²) = 10⁴ steps is nothing (TLE starts around 10⁸). So the brute force passes. We learn the optimal one for interviews.
• At least 1 value, so the tree is never empty and preorder[0] always exists.
• Values are between 1 and 1000 and all distinct, so we never need to decide which side an equal value goes on. They're small enough that "infinity" can safely be any big number. We use float('inf'); the teacher uses the max int.

3Intuition

The first value is the root. Everything after it splits into two blocks: first the values smaller than the root (left subtree), then the rest (right subtree). So: make the root, find where the smaller block ends, and build the left subtree from the first block and the right subtree from the second, using the same function. Each block is itself a preorder of a smaller BST, so the same rule applies inside it.

4Building the logic from the example

Where does the left block end?

We can't know the left block's size in advance. Maybe only 5 is on the left and everything else is on the right. Maybe everything is on the left and the right is empty. The teacher's way to find it: use the definition. Left-subtree values are smaller than the root. So start right after the root and move forward while the values are smaller than 8:

• 5 < 8 ✓ · 1 < 8 ✓ · 7 < 8 ✓ · 10 < 8 ✗ → stop. The stop index i points at 10.
• Left block = from start + 1 to i − 1 → [5, 1, 7]
• Right block = from i to end → [10, 12]

So we pass the whole preorder list plus two indexes (start, end) that say which part to build from. We don't make new copies of the list.

The base case is on the indexes, not on a node

Usually the base case is "if root is None". Here there's no tree yet. We are creating nodes from index ranges, so the stop condition must be about the indexes:

• start == end: one value. Make a node, and both of its blocks will turn out empty.
• start > end: an empty range, nothing to build → return None. The parent is waiting to store a TreeNode in root.left / root.right, and None is the "no node" answer.

Don't run off the end of the range while scanning

What if every remaining value is smaller than the root (everything goes left, the right is empty)? Then the "smaller than root" check never fails and i would walk out of the range. So the loop must also check that i is still inside the range.

Always return the root you made

Building works on the way back up. When we create 5, it isn't attached to 8 yet. It's attached only when its call returns it and the parent stores it in root.left. The same goes for 1 and 7 hanging under 5.

5Approach steps

1. build(start, end): if start > end → return None.
2. Make root from preorder[start].
3. Scan i from start + 1 while i <= end and preorder[i] < root.val.
4. root.left = build(start + 1, i − 1), root.right = build(i, end).
5. Return root. Start with build(0, n − 1).

6Code (Python)

class Solution:
    def bstFromPreorder(self, preorder):
        return self.build(preorder, 0, len(preorder) - 1)

    def build(self, preorder, start, end):
        if start > end:                     # empty range
            return None
        root = TreeNode(preorder[start])     # first value = root
        i = start + 1
        while i <= end and preorder[i] < root.val:   # <= (fixed)
            i += 1
        root.left = self.build(preorder, start + 1, i - 1)
        root.right = self.build(preorder, i, end)
        return root                          # this is what connects it

7Code line by line

8Dry run (hand table)

preorder = [8, 5, 1, 7, 10, 12], indexes 0–5.

Connections happen on the way back: 1 and 7 attach to 5 when their calls return, then 5 attaches to 8. 12 attaches to 10, then 10 attaches to 8. Result: Example 1's tree ✓

9Complexity & remember

• Time O(n²): creating the n nodes is O(n), but at every node we also run the scan to find the split, which can be close to n long. A loop inside every call → O(n) × O(n). The worst case is a chain-shaped tree (e.g. preorder sorted in decreasing order), where the scans are n−1, n−2, …, giving about n²/2. For n = 100 that's only about 10⁴ steps, so it's still fast here.
• Space O(h) for the recursion: log n if balanced, n if skewed.

Part B · Optimal: one pass with an upper bound

1The question

Same problem. Now we want to stop searching for the split point. The extra scan is the only thing making Part A O(n²).

2Constraints

Same as Part A. The goal now is O(n), which is what an interviewer will expect.

3Intuition: take values one by one and ask "do you fit here?"

Don't split the list at all. Walk through it with one pointer i, from left to right, and place each value as you go:

• Take 8 → make it the root.
• Take 5 → it's smaller than 8, so it belongs on 8's left. Try to place it there.
• And so on. Each spot in the tree has an upper bound: a value that whatever sits in that spot must not go past. If the current value is over the bound, it doesn't belong here. Return None, and some spot higher up will take it.

4Building the conditions from examples

What bound does a left child get?

Going to 8's left, everything placed there must be smaller than 8. So the left call gets bound = root.val (8).

What bound does a right child get?

Going to a node's right, values can be bigger than the node. But how much bigger? The teacher's reasoning: the right child inherits its parent's bound. Say a node's own bound is 20 (it lives in the left subtree of 20). Its right child can be bigger than the node, but it's still inside 20's left subtree, so it must stay under 20. For the root, the bound is ∞, so the root's right child is limited only by ∞.

The two "don't place it" conditions

1. The list is used up: i == len(preorder). There's no value left to place, so return None. If the values are smaller and smaller (all going left), the bound check would never fail, and without this check we'd read past the end of the list.
2. The value doesn't fit: preorder[i] > bound. It can't live in this spot → return None, and don't move i. The value stays waiting for the right spot.

And as in Part A, every call ends with return root, so the node gets attached to its parent on the way back.

5Approach steps

1. Keep a shared pointer self.i = 0.
2. build(bound): if i == n or preorder[i] > bound → return None.
3. Make root = TreeNode(preorder[i]) and move i forward.
4. root.left = build(root.val)
5. root.right = build(bound), using the same bound this call received.
6. Return root. Start with build(∞).

6Code (Python)

class Solution:
    def bstFromPreorder(self, preorder):
        self.i = 0                               # next value waiting for a spot
        return self.build(preorder, float('inf'))

    def build(self, preorder, bound):
        if self.i == len(preorder) or preorder[self.i] > bound:
            return None                          # nothing left / doesn't fit here
        root = TreeNode(preorder[self.i])
        self.i += 1
        root.left = self.build(preorder, root.val)   # left: must stay under me
        root.right = self.build(preorder, bound)     # right: my parent's limit
        return root

7Code line by line

8Dry run: the teacher's full walk with bounds

preorder = [8, 5, 1, 7, 10, 12]. "b" = the bound for that call. i = index of the waiting value.

1. build(b=∞), i=0 → 8 ≤ ∞ → create 8, i=1 → go left with b=8.
2. build(b=8) → 5 ≤ 8 → create 5 (not yet attached), i=2 → go left with b=5.
3. build(b=5) → 1 ≤ 5 → create 1, i=3 → go left with b=1.
4. build(b=1) → value 7 > 1 → None. 1.left = None. i stays at 3 (7 still waiting).
5. 1 goes right with its parent's bound, b=5 → 7 > 5 → None. 7 can't be 1's right child, because 1 sits in 5's left subtree. 1 returns itself → 5.left = 1.
6. 5 goes right with its bound, b=8 → 7 ≤ 8 → create 7, i=4.
7. 7 left (b=7): 10 > 7 → None. 7 right (b=8): 10 > 8 → None. 7 returns → 5.right = 7. 5 returns → 8.left = 5.
8. 8 goes right with b=∞ → 10 ≤ ∞ → create 10, i=5.
9. 10 left (b=10): 12 > 10 → None. 10 right (b=∞): 12 → create 12, i=6.
10. 12 left (b=12): i == 6 == n → None. 12 right (b=∞): i == n → None. 12 returns → 10.right = 12. 10 returns → 8.right = 10.
11. 8 returns to the main function. The stack is empty. The tree is Example 1's tree ✓

Notice how 7 tried 1's left (no), then 1's right (no), then found its place at 5's right. Failed tries cost O(1) each.

9Complexity & remember

• Time O(n): every value is turned into a node exactly once (the pointer only moves forward). The only extra work is the "doesn't fit → None" calls. Each one costs O(1), and each one fills one empty child spot. A tree of n nodes has only n + 1 empty spots, so that's O(n) more. In total O(n). The split-point scan is gone.
• Space O(h): the recursion stack. log n for a balanced BST, n for a skewed one.

Part C · Revision page

def pre(r):
    return [] if r is None else [r.val] + pre(r.left) + pre(r.right)
def ino(r):
    return [] if r is None else ino(r.left) + [r.val] + ino(r.right)

for p in ([8, 5, 1, 7, 10, 12], [1, 3], [3, 2, 1], [5]):
    t = Solution().bstFromPreorder(p)
    print(pre(t) == p, ino(t) == sorted(p))   # True True each time

Based on this video: Construct Binary Search Tree from Preorder Traversal