MEDIUM

Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree and two nodes p and q known to exist in it, return their lowest common ancestor — the deepest node that has both as descendants (a node counts as its own descendant).

Example

Input root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8

Output 6

Key Pointers

BST ordering lets you decide direction without inspecting subtrees: both target values less than the current node means go left, both greater means go right.
The first node where p and q "split" (one on each side, or one equal to the node) is the LCA — no need to explore both branches.
This runs in O(h) instead of the O(n) a generic-tree LCA needs, because BST structure prunes the search.

Step-by-Step Analysis

Start at root.
If both p.val and q.val are less than the current node's value, move to its left child and repeat.
If both are greater, move to its right child and repeat.
Otherwise the values split across the current node (or one equals it) — that node is the LCA, return it.

Complexity

Time: O(h) — Space: O(1) iterative

Code

def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    node = root
    while node:
        if p.val < node.val and q.val < node.val:
            node = node.left
        elif p.val > node.val and q.val > node.val:
            node = node.right
        else:
            return node
    return None

Code Explanation

How the solution above works, piece by piece.

Start at the root and walk down; no recursion is needed.
Both values smaller than the node: both are in the left subtree, so the ancestor is lower on the left.
Both larger: go right.
Otherwise they split here (or one of them is this node): this is the lowest node with both below it.
O(height) time, O(1) space. It uses the BST ordering; a plain binary tree needs a full search.

Visual Walkthrough

Running it on the example tree with p = 2, q = 8:

In a BST, smaller values are left and larger right. While p and q are on the same side, walk that way. The first node where they split (or equal one of them) is the lowest common ancestor; here it's the root.

LCAp and q

Video Explanation

NeetCode — LeetCode 235