DSA With AI
Week 4 ยท Trees

Lowest Common Ancestor of a Binary Search Tree

Given a BST and two target nodes, return the lowest node that has both targets in its subtree. The runner passes target values and returns the LCA value.

Medium Trees Week 4 Practice runner

Frame the problem

  • The tree is a valid BST.
  • Both targets exist in the common version.
  • A node can be an ancestor of itself.
1. Reveal example inputs and outputs

Example 1

Input:

lowest_common_ancestor_bst([
  6,
  [
    2,
    [
      0,
      null,
      null
    ],
    [
      4,
      [
        3,
        null,
        null
      ],
      [
        5,
        null,
        null
      ]
    ]
  ],
  [
    8,
    [
      7,
      null,
      null
    ],
    [
      9,
      null,
      null
    ]
  ]
], 2, 8)

Output:

6

Example 2

Input:

lowest_common_ancestor_bst([
  6,
  [
    2,
    [
      0,
      null,
      null
    ],
    [
      4,
      [
        3,
        null,
        null
      ],
      [
        5,
        null,
        null
      ]
    ]
  ],
  [
    8,
    [
      7,
      null,
      null
    ],
    [
      9,
      null,
      null
    ]
  ]
], 2, 4)

Output:

2
2. Brute force first

How would you solve this in a normal binary tree? Which extra BST ordering fact lets you avoid searching both sides?

3. Reveal the insight ladder
  1. If both targets are smaller than the current value, the LCA must be in the left subtree.
  2. If both targets are larger, the LCA must be in the right subtree.
  3. Otherwise the current node splits the targets or equals one target.
  4. That split point is the lowest common ancestor.
4. Dry run before code
  1. At root 6 with targets 2 and 8, one target is left and one is right.
  2. The split happens immediately.
  3. Return 6.
  4. With targets 2 and 4, current 6 moves left to 2; 2 equals a target, so return 2.
5. Reveal final Python solution 
def lowest_common_ancestor_bst(root, p, q):
    low, high = sorted((p, q))
    node = root
    while node:
        value, left, right = node
        if high < value:
            node = left
        elif low > value:
            node = right
        else:
            return value

Complexity: Time O(h), where h is tree height. Space O(1) for the iterative version.

Interview narration

  • I will use the BST property to choose one direction at a time.
  • The first node where the targets split is the lowest possible common ancestor.
  • If the current node equals one target, it is the LCA because the other target lies below it.

Common traps

  • Solving it as a general binary-tree problem and doing extra work.
  • Using strict movement rules that skip the case where current equals p or q.
  • Forgetting that the static runner uses values, while LeetCode passes node objects.

Follow-up drills

1. How does the general binary-tree LCA differ?

You recursively search both children. If both sides return a target, the current node is the LCA; if one side returns a node, bubble it up.

2. What if one target may be missing?

You need either a preliminary existence check or a recursive result that tracks whether both targets were found before returning an LCA.

3. Why is this O(h) instead of O(n)?

The BST ordering lets you discard one whole subtree at each step until the split point.

Interactive runner

Write the required Python function. Your code runs locally in this browser. Hints reveal one failing case at a time.