DSA sheet · Trees · BST pattern

Convert Sorted Array to BST

This is the first problem of the BST pattern. The teacher uses it to introduce what a binary search tree is, and then shows how to build one from a sorted list of numbers. The main idea is pick the middle number as the root, then do the same for each half. It is the same "cut in half" thinking as binary search. You will also learn a habit that every tree-building problem needs: attach what the recursive call returns to root.left / root.right, and always return the node you made.

Every problem 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 (BST, inorder, height balanced)
• Part A · Sorted Array to BST with DFS (recursion)
• Part B · Revision page

Part 0 · Before starting

What is a tree node?

Each node is a small box with 3 things: its value, a link to its left child and a link to its right child. A missing child is None.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val       # the number in this node
        self.left = left     # left child, or None
        self.right = right   # right child, or None

What is a Binary Search Tree (BST)?

A BST is a normal binary tree with one extra rule about where numbers are allowed to sit:

          5
        /   \
       2     8
      / \   / \
     1   4 6   9

Check node 5: its left side has 2, 1, 4, all smaller than 5 ✓. Its right side has 8, 6, 9, all bigger ✓. Now check node 2: left has 1 (smaller ✓), right has 4 (bigger ✓). The same rule must hold at 8, and at every other node.

          5
        /   \
       2     8
        \
         7       ← 7 > 2, fine for its parent…
                  …but 7 > 5 and it sits on 5's LEFT side ✗

So 7 breaks the rule for 5. Every node's value must fit the limits set by all of its ancestors (parent, grandparent, and so on up to the root), not only its parent.

Why the inorder of a BST is sorted

Inorder traversal means: visit the left subtree, then the node, then the right subtree (and do the same inside each subtree). For a BST:

• Everything in the left subtree is smaller, and it is printed first.
• Then the node itself.
• Then everything in the right subtree, which is bigger, printed last.

The same thing happens inside every subtree, so the full output comes out in increasing order. For the tree above, inorder gives 1 2 4 5 6 8 9.

This problem is that fact run backwards. We are given the sorted list, which is the inorder of the tree we want, and we must build the tree.

Height and "height balanced"

• Height of a tree = the number of nodes on the longest path from the root down to a leaf (a leaf is a node with no children). A single node has height 1, an empty tree has height 0.
• A tree is height balanced when, at every node, the heights of the left and right subtrees differ by at most 1. (This was its own problem earlier in the Binary Tree playlist: "Balanced Binary Tree".)

Part A · Sorted Array to BST with DFS

LeetCode 108 · Convert Sorted Array to Binary Search Tree

1The question in simple words

You get a list nums sorted in increasing order. Build a BST that holds all these numbers, and make it height balanced. Return its root.

Example: nums = [-10, -3, 0, 5, 9]. One correct answer:

          0
        /   \
     -10     5
        \     \
        -3     9

The question accepts any height-balanced BST, so more than one answer can be correct.

2What the constraints tell us

• 1 ≤ nums.length ≤ 10⁴ → the number of nodes we must build is between 1 and 10⁴. The list is never empty, so the tree will have at least a root.
• Values from −10⁴ to 10⁴ → small. An int holds up to about 10⁹, so no need for long (and Python ints never overflow anyway).
• The list is sorted. When a question bothers to say "sorted", it is a strong hint. The teacher's first thought is binary search.
• We have to create n nodes, so we can't do better than O(n). That is our target.

3Intuition: how to think about it

Many BSTs can be made from the same list

The teacher first shows that the root can be almost anything. Try a few roots with [-10, -3, 0, 5, 9]:

-10
   \
   -3
     \
      0
       \
        5
         \
          9

     -3
    /  \
 -10    0
         \
          5
           \
            9

       0
     /   \
   -3     5
   /       \
 -10        9

All three are valid BSTs. Each new number just goes left if it's smaller and right if it's bigger. But the question also wants height balanced, so most of these fail.

Take the tree with root −3. Its left side is just −10, so the left height is 1. Its right side is 0 → 5 → 9, so the right height is 3. The difference is 2, which is more than 1 → not balanced.

The fix: choose the middle

If the root is the middle number, half the numbers are smaller and half are bigger. Because the list is sorted:

• everything to the left of the middle in the list is smaller → it becomes the left subtree,
• everything to the right of the middle is bigger → it becomes the right subtree.

The two halves have almost the same size, so the two sides get almost the same height. Then we do the same thing again for each half: take its middle as the root of that subtree, and so on. It's like binary search, but instead of throwing one half away, we build both halves.

  [-10, -3,  0,  5,  9]
             ↑ middle → root
  [-10, -3]     [5, 9]
   left half    right half
   → left        → right
     subtree       subtree

The BST rule is automatically true: every number that goes to the left half really is smaller than the root, because the list is sorted.

4Building the logic step by step

What does our function receive? Not a root!

In most tree problems the function gets a root. Here there is no tree yet. We are the ones creating it. What we do have is the list. So the function gets the list and two indexes: left and right, which mark the part of the list we still have to turn into a subtree.

• First call: the whole list, left = 0, right = len(nums) - 1.
• Later calls: only a piece of the list (a half, a quarter…).

Base case: when do we stop?

Recursion needs a condition that stops it. Here the indexes give us that condition:

• left == right → the piece has exactly one number. We can still make a node from it, so keep going.
• left > right → the pointers have crossed. The piece is empty and there is nothing to make.

What do we return for an empty piece? The caller will put our answer into root.left or root.right. Those slots can hold only a node or None. No node here, so return None.

Find the middle index

mid = left + (right - left) // 2

Make the root, then build both sides

Make a node from the middle number: root = TreeNode(nums[mid]). Now the two halves:

• Numbers smaller than it are at indexes left … mid-1 → build them and put the result in root.left.
• Numbers bigger than it are at indexes mid+1 … right → build them and put the result in root.right.

The list stays the same in every call. Only left and right change.

Return the root: this is when nodes get connected

After both sides are built, return root. The teacher stresses this point. When a call creates a node, that node is not yet attached to anything. It gets attached only when the call returns it and the parent stores it in its .left or .right.

Example from the dry run: the call that builds −3 makes the node, its two children are None, and then it returns −3. Only then does the call for −10 store it: (-10).right = -3. Without return root, the parent would receive None and the tree would fall apart.

5Approach steps (the algorithm in plain English)

1. Call build(0, len(nums) - 1) and return what it gives.
2. Inside build(left, right): if left > right, the piece is empty → return None.
3. Find mid = left + (right - left) // 2.
4. Make root = TreeNode(nums[mid]).
5. root.left = build(left, mid - 1) (the smaller half).
6. root.right = build(mid + 1, right) (the bigger half).
7. Return root to the parent so it gets connected.

6Code (Python)

class Solution:
    def sortedArrayToBST(self, nums):
        return self.build(nums, 0, len(nums) - 1)

    def build(self, nums, left, right):
        if left > right:                       # empty piece -> no node
            return None
        mid = left + (right - left) // 2       # middle index (safe form)
        root = TreeNode(nums[mid])             # middle number becomes the root
        root.left = self.build(nums, left, mid - 1)    # smaller half
        root.right = self.build(nums, mid + 1, right)  # bigger half
        return root                            # hand it to the parent

7Code line by line

8Dry run using the call stack

nums = [-10, -3, 0, 5, 9], indexes 0 to 4. b(l, r) means build(nums, l, r).

1. b(0, 4): mid = 0 + 4//2 = 2 → make node 0. Go left first. (b(0,4) waits on the stack.)
2. b(0, 1): mid = 0 + 1//2 = 0 → make node −10. Go left. (b(0,1) waits.)
3. b(0, −1): left 0 > right −1 → crossed → return None. So (−10).left = None.
4. Back in b(0,1), go right: b(1, 1): one number left, mid = 1 → make node −3.
5. Inside b(1,1): left call b(1, 0) → crossed → None. Right call b(2, 1) → crossed → None. −3 is a leaf.
6. b(1,1) returns −3. Now (−10).right = −3 gets connected.
7. b(0,1) returns −10 (with −3 hanging on its right). Now (0).left = −10 gets connected.
8. Back in b(0,4), go right: b(3, 4): mid = 3 + 1//2 = 3 → make node 5.
9. b(3,4) left: b(3, 2) → crossed → None. Right: b(4, 4) → make 9, its children b(4,3) and b(5,4) are both None → returns 9. So (5).right = 9.
10. b(3,4) returns 5 → (0).right = 5. b(0,4) returns 0, the root of the whole tree. Done ✓

The newest call is on top (red). A node only joins its parent when its call returns and leaves the stack.

  final tree:      0
                 /   \
              -10     5
                 \     \
                 -3     9
  left height = 3 (0, -10, -3)   right height = 3 (0, 5, 9)   difference 0 ✓

Inorder of this tree: −10, −3, 0, 5, 9, exactly the input list ✓. So it's a correct BST, and it's balanced.

9Complexity & remember

• Time O(n). The list is sorted, but that doesn't let us skip anything: every number must become a node, and each one is created exactly once. n numbers → n calls that do real work (plus the None calls, at most n + 1) → O(n).
• Space O(log n) for the call stack. At any moment the stack holds one call per level of the path we're on, and finished calls are removed. Because we always split in the middle, the tree is balanced and its height is about log₂ n. (The n nodes we create are the answer itself, so they're usually not counted as extra space.)

Why not BFS here?

The teacher says DFS is the natural fit. BFS moves through a tree level by level. But this problem isn't about levels. The work at each node is "this number is the root, now send the smaller numbers to the left side and the bigger numbers to the right side". That is a split and recurse job, so recursion matches it directly.

from collections import deque

class SolutionQueue:
    def sortedArrayToBST(self, nums):
        if not nums:
            return None
        mid = (len(nums) - 1) // 2
        root = TreeNode(nums[mid])
        queue = deque([(root, 0, len(nums) - 1)])   # node + the range it came from
        while queue:
            node, left, right = queue.popleft()
            mid = left + (right - left) // 2        # node's own index
            if left <= mid - 1:                     # numbers left for a left child
                m = left + (mid - 1 - left) // 2
                node.left = TreeNode(nums[m])
                queue.append((node.left, left, mid - 1))
            if mid + 1 <= right:                    # numbers left for a right child
                m = mid + 1 + (right - mid - 1) // 2
                node.right = TreeNode(nums[m])
                queue.append((node.right, mid + 1, right))
        return root

Part B · Revision page

def inorder(node):
    return inorder(node.left) + [node.val] + inorder(node.right) if node else []

def height(node):
    return 1 + max(height(node.left), height(node.right)) if node else 0

s = Solution()
root = s.sortedArrayToBST([-10, -3, 0, 5, 9])
print(root.val, root.left.val, root.left.right.val, root.right.val, root.right.right.val)  # 0 -10 -3 5 9
print(inorder(root))                              # [-10, -3, 0, 5, 9]
print(height(root.left), height(root.right))      # 2 2
print(inorder(s.sortedArrayToBST([7])))           # [7]
print(inorder(s.sortedArrayToBST([1, 3])))        # [1, 3]

Based on this video: Convert Sorted Array to Binary Search Tree