DSA sheet · Binary Search Tree · LCA pattern

LCA of a BST

This video takes the "lowest common ancestor" problem we already solved for a normal binary tree and asks it again for a binary search tree. The big lesson: the BST ordering tells us which side to walk into, so we never have to search both sides. That turns a "visit everything" solution into a "walk one path down" solution. The teacher first writes it with recursion, then shows how an interviewer's "now make the space constant" request leads to a tiny while loop version.

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 · LCA of a BST with recursion
• Part B · LCA of a BST with a while loop (constant space)
• Part C · 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
        self.left = left
        self.right = right

What is a Binary Search Tree (BST)?

A BST is a binary tree with one extra promise, true at every node:

• Every value in the node's left subtree (the child on the left and everything below it) is smaller than the node.
• Every value in the node's right subtree (the right child and everything below it) is bigger than the node.

Short form: left subtree < node < right subtree. Note the word subtree: it's not enough that the direct children obey it. The grandchildren, great-grandchildren and so on must obey it too.

            6
          /   \
         2     8
        / \   / \
       0   4 7   9
          / \
         3   5

This is the tree used all through the video (LeetCode 235's example). Check node 6: everything on its left (2, 0, 4, 3, 5) is smaller than 6, and everything on its right (8, 7, 9) is bigger. Check node 2: left side 0 is smaller, right side 4, 3, 5 are all bigger. It holds everywhere.

Why this helps: a BST is like a signpost at every node

Standing at a node, if you want a value smaller than the node, it can only be on the left. If you want a bigger value, it can only be on the right. So you never need to look at both sides. This is the same idea as binary search on a sorted array: at each step you throw away half.

Ancestor, common ancestor, lowest common ancestor

• An ancestor of a node is any node on the path from the root down to it: its parent, its parent's parent, and so on. By LeetCode's rule, a node also counts as its own ancestor.
• A common ancestor of p and q is a node that is an ancestor of both.
• The lowest common ancestor (LCA) is the common ancestor that is deepest in the tree (farthest from the root). Think of it as the nearest shared parent.

In the tree above: LCA(2, 8) = 6. LCA(0, 4) = 2. LCA(7, 9) = 8. And LCA(2, 4) = 2, because 2 is an ancestor of 4 and also of itself.

What changes from the normal binary-tree LCA (previous video)

In a normal binary tree we had no idea whether p and q were on the left or the right, so we had to search both sides of every node and combine the answers. That costs O(n). Here the BST rule tells us the side straight away, so we follow a single path downward.

Part A · LCA of a BST with recursion

LeetCode 235 · Lowest Common Ancestor of a Binary Search Tree

1The question in simple words

You get the root of a BST and two nodes p and q that are in the tree. Return the node that is their lowest common ancestor.

         6
       /   \
      2     8
     / \   / \
    0   4 7   9

         6
       /   \
      2     8
     / \   / \
    0   4 7   9

         6
       /   \
      2     8
     / \   / \
    0   4 7   9

2What the constraints tell us

• Number of nodes: 2 to 10⁵. At least two nodes, which makes sense since p and q must both be in the tree.
• 10⁵ nodes means O(n²) = 10¹⁰ operations, far beyond the ~10⁸ limit, so it would surely get TLE. We need O(n) or O(n log n) at worst, and less if we can. Thanks to the BST rule, we can do better than linear on a balanced tree.
• Values: −10⁹ to 10⁹. That fits in a normal 32-bit int. We only compare values, we never add or multiply them, so there's no overflow risk and no need for long. (Python ints never overflow anyway.)
• All values are unique, p ≠ q, and both are in the tree. Remember the "unique" part; it comes back in Part B.

3Intuition: the place where p and q split up

Picture p and q as two travellers starting at the root. At each node, each traveller follows the signpost: smaller goes left, bigger goes right.

• As long as the signposts send both travellers the same way, they walk together, and the current node is a common ancestor but not the lowest one.
• The first node where they would have to go different ways (one left, one right) is where their paths split. That node is the lowest common ancestor. Below it, no node can be above both of them.
• Also, if the current node is p or q, the walk stops there: that node is an ancestor of the other one, so it's the answer.

4Building the conditions from examples

The teacher discovers each case with one pair of nodes.

Example p = 0, q = 4 → both smaller → go left

We stand at 6. The bigger of p and q is 4, and 6 is bigger than even that. So 6 is bigger than both: 0 and 4 must both be in 6's left subtree. We can ignore the right side completely and ask the same question at 2.

Example p = 7, q = 9 → both bigger → go right

At 6, the smaller of p and q is 7, and 6 is smaller than even that. So 6 is smaller than both: 7 and 9 are both in the right subtree. Go right, to 8.

Back to p = 0, q = 4, now standing at 2 → neither case → this is the answer

Is 2 bigger than both? 2 is bigger than 0, but not bigger than 4. So not case 1. Is 2 smaller than both? It's smaller than 4, but not smaller than 0. So not case 2. That means 0 is on 2's left and 4 is on 2's right. The travellers split here, so 2 is the LCA. We return it without going any lower.

The same happens with p = 2, q = 8 right at the root: 6 is not bigger than 8 and not smaller than 2, so 6 is the answer immediately.

5Approach steps

1. Look at the current node root.
2. If its value is bigger than both p and q → return the answer from the left subtree (same function, called on root.left).
3. Else if its value is smaller than both → return the answer from the right subtree.
4. Otherwise → p and q split here (or one of them is here) → return root.

6Code (Python)

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        if root is None:                                  # safety only
            return None
        if root.val > p.val and root.val > q.val:         # both on the left
            return self.lowestCommonAncestor(root.left, p, q)
        if root.val < p.val and root.val < q.val:         # both on the right
            return self.lowestCommonAncestor(root.right, p, q)
        return root                                       # they split here

7Code line by line

8Dry run using the call stack

Run 1: p = 2, q = 8.

1. Call f(6): is 6 bigger than both 2 and 8? No. Smaller than both? No. → return 6. Done in a single call.

Run 2: p = 7, q = 9.

1. Call f(6): 6 > 7 and 6 > 9? No. 6 < 7 and 6 < 9? Yes → call f(6.right) = f(8). f(6) waits on the stack.
2. Call f(8): 8 > 7 but not > 9 → not case 1. 8 < 9 but not < 7 → not case 2. → return 8.
3. f(6) receives 8 and returns it unchanged. The stack is empty. Final answer: 8 ✓

Run 3: p = 0, q = 4. f(6): bigger than both → f(2). f(2): bigger than 0 but not 4, smaller than 4 but not 0 → return 2. f(6) passes 2 up. Answer 2 ✓.

Notice: at each level we called the function on only one child. In the normal binary-tree LCA we called both.

9Complexity & remember

• Time O(h), where h is the height (number of levels). We visit one node per level.
  • Balanced BST: h ≈ log n → O(log n).
  • Skewed BST (every node has only a right child, like 1 → 2 → 3 → 4 …): it's really a line, so the number of levels equals the number of nodes → O(n).
• Space O(h): each recursive call waits on the call stack, one per level. So O(log n) for a balanced tree, O(n) for a skewed one.

Part B · LCA of a BST with a while loop (constant space)

Same question, same constraints, same three cases as Part A. Only the way we move changes.

1Why make an iterative version?

The teacher's interview tip: the interviewer may say "the time is fine, but bring the space down to constant". Whenever you hear constant space, drop the recursion, because recursion always uses the call stack. Instead, keep one variable pointing at the current node and move it down inside a while loop.

2Why is this so easy here?

Look at Part A: every recursive call is the last thing the function does (return self.f(child)). The parent never does any work after the child answers; it just passes the answer up. So we don't need to remember the parents at all. We can simply replace root with the child and loop again.

3The conditions (unchanged)

• Smaller than both → root = root.right.
• Bigger than both → root = root.left.
• Otherwise → return root.
• If the loop ever ends (root became None) → return None. With valid input this never happens, but the method must return a node or nothing.

4Approach steps

1. While root is not None:
2. If root.val < p.val and root.val < q.val → move root to its right child.
3. Else if root.val > p.val and root.val > q.val → move root to its left child.
4. Else → return root.
5. After the loop → return None.

5Code (Python)

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        while root is not None:
            if root.val < p.val and root.val < q.val:     # both on the right
                root = root.right
            elif root.val > p.val and root.val > q.val:   # both on the left
                root = root.left
            else:                                         # they split here
                return root
        return None

6Code line by line

7Dry run: a hand table

Tree from Part 0, p = 3, q = 5 (both deep in the tree):

3 is on 4's left and 5 is on 4's right, so 4 is where they split ✓. We touched only 3 nodes, one per level, out of 9.

8Complexity

• Time O(h): O(log n) for a balanced BST, O(n) for a skewed one. Same as Part A.
• Space O(1): just the one root variable. No call stack. That's the improvement over Part A, which needed O(h).

Part C · Revision page

n3, n5 = TreeNode(3), TreeNode(5)
n4 = TreeNode(4, n3, n5)
n0 = TreeNode(0)
n2 = TreeNode(2, n0, n4)
n7, n9 = TreeNode(7), TreeNode(9)
n8 = TreeNode(8, n7, n9)
root = TreeNode(6, n2, n8)

s = Solution()
print(s.lowestCommonAncestor(root, n2, n8).val)   # 6
print(s.lowestCommonAncestor(root, n0, n4).val)   # 2
print(s.lowestCommonAncestor(root, n7, n9).val)   # 8
print(s.lowestCommonAncestor(root, n2, n4).val)   # 2  (a node is its own ancestor)
print(s.lowestCommonAncestor(root, root, n2).val) # 6
print(s.lowestCommonAncestor(root, n3, n5).val)   # 4

Based on this video: LCA of a Binary Search Tree