Lowest Common Ancestor of a Binary Search Tree

If both target values are less than the current node, the LCA must be in the left subtree. If both are greater, it must be in the right subtree. Otherwise the current node is exactly where the two paths diverge (or one target is the current node) — that is the LCA.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        if p.val < root.val and q.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)
        if p.val > root.val and q.val > root.val:
            return self.lowestCommonAncestor(root.right, p, q)
        return root

Complexity: the walk follows a single downward path from root to the LCA, never branching → O(h) time, where h is the tree height (O(log n) for a balanced BST, O(n) skewed). Recursion depth matches → O(h) space.

The recursion above is tail recursion — at each step it just moves to a child and repeats. That translates directly into a loop with no extra stack frames.

class Solution:
    def lowestCommonAncestor(self, 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

Watch the walk descend and prune at each step (trace data lives in this problem folder’s data.ts):

Why prefer this: identical O(h) time, but no call stack is used at all → O(1) space, an improvement over the recursive version’s O(h) stack, which matters on a very deep, unbalanced BST.