Lowest Common Ancestor in a BST

Interview Problem Interview Medium Binary Search Tree Search

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.lowestCommonAncestor(root, pValue, qValue). Values identify two existing BST nodes. Return the value of their lowest common ancestor; this value-based contract makes the node result serializable.

Starter code

class Solution:
    def lowestCommonAncestor(self, root, pValue, qValue):
        pass

Test cases

root-split

{
  "args": [
    {
      "$type": "binary-tree",
      "values": [
        6,
        2,
        8,
        0,
        4,
        7,
        9,
        null,
        null,
        3,
        5
      ]
    },
    2,
    8
  ]
}

Expected: 6

Wizard outline

Step 1: Initialize Solution.lowestCommonAncestor
Replace the empty starter with the first real state owned by Solution.lowestCommonAncestor. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Pass the Root Split case
Complete the readable core algorithm for one representative Interview case. Move left when both targets are smaller, right when both are larger, otherwise stop at their split.
Step 3: Harden the Target Is Ancestor boundary
Repair the reviewed boundary and pass the complete submission contract. When both targets lie on one ordered side, their LCA must also lie there. The first node where they split or equal the current node is an ancestor of both and no descendant can remain ancestor of both, making it lowest.

Footguns and prerequisites

A target can itself be the ancestor and must be returned at equality.
trees and graphs

Reviewed references

LeetCode 235 — Lowest Common Ancestor of a Binary Search Tree

Practice prerequisites

Carry State Through Tree DFS(opens in a new tab)
Carry State Through Tree DFS isolates the running total passed to a node equals the sum from the root through that node, independent of sibling branches. That focused state discipline is required when implementing lowest common ancestor bst as a complete Interview Problem.

Recommended approach and implementation

Normalize lower/higher target values and walk from root: go left above both, right below both, otherwise return the current split value.

Why it works: When both targets lie on one ordered side, their LCA must also lie there. The first node where they split or equal the current node is an ancestor of both and no descendant can remain ancestor of both, making it lowest.

class Solution:
    def lowestCommonAncestor(self, root, pValue, qValue):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        lower, higher = sorted((pValue, qValue))
        current = root
        while current:
            if current.val < lower:
                current = current.right
            elif current.val > higher:
                current = current.left
            else:
                return current.val