ToolMight LogoToolMight
EasyTrees & BSTPattern: BST Invariant TraversalPattern: Divide and Conquer

Lowest Common Ancestor of a Binary Search Tree

Find the lowest common ancestor (LCA) node of two given nodes in a Binary Search Tree. Exploit BST ordering properties to find the split point in O(h) time.

Problem Statement

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

According to the definition of LCA on Wikipedia: "The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself)."

Examples & Constraints

Example 1
Input: root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6 because 2 is in the left subtree and 8 is in the right subtree.
Example 2
Input: root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
Constraints
  • The number of nodes in the tree is in the range [2, 10^5].
  • -10^9 <= Node.val <= 10^9
  • All Node.val are unique.
  • p != q
  • p and q will exist in the BST.

BST Invariant Split Point Walk

Optimal Approach
Time:O(h)
Space:O(1)

Start at the root and navigate downward. The first node where p and q diverge to opposite sides (or where the node equals p or q) is the Lowest Common Ancestor.

Time ComplexityO(h)

We descend one level per iteration. At most H steps are taken where H is tree height: O(log n) for balanced BST, O(n) for skewed BST.

Space ComplexityO(1)

Operates iteratively with a single pointer variable. Zero extra call stack memory allocated.

Underlying algorithmic logic

The Power of Binary Search Tree Properties

In a general binary tree, finding LCA requires searching both branches exhaustively with post-order traversal.

However, a Binary Search Tree (BST) satisfies strict ordering:

  • All values in the left subtree are strictly smaller than root.val.
  • All values in the right subtree are strictly greater than root.val.

The Three Decision Cases:

Starting at curr = root:

  1. Both nodes are smaller: If p.val < curr.val and q.val < curr.val, then both p and q must reside exclusively in the left subtree. Move curr = curr.left.
  2. Both nodes are larger: If p.val > curr.val and q.val > curr.val, then both p and q must reside exclusively in the right subtree. Move curr = curr.right.
  3. The Split Point: If one value is on the left and the other is on the right (or if curr.val equals p.val or q.val), curr is the highest point where their paths divide! This curr node is guaranteed to be the Lowest Common Ancestor.

Iterative vs Recursive

This decision path is a single downward walk through the tree height. We can implement it iteratively in O(1) auxiliary space with zero recursion call stack overhead!

Step-by-step execution walkthrough

1
Start at Root (6)

Target p = 2, q = 8. Check: 2 < 6, but 8 > 6. One node is smaller, one is greater!

Split detected at node 6 -> LCA is 6
2
Second Example (p = 2, q = 4)

Start at Root (6). Both 2 < 6 and 4 < 6. Move curr to left child (2).

curr = 2
3
Inspect Node (2)

p equals curr (2). q (4) > 2. curr matches p. Descents stop.

Node 2 is ancestor of itself and 4 -> LCA is 2
Advantages
  • •Optimal O(1) auxiliary space when implemented iteratively
  • •Leverages BST property to avoid traversing unnecessary subtrees
Trade-offs
  • •Relies on the BST sorted invariant; does not apply directly to general binary trees

Code Implementations

Copy & paste production-ready solutions for BST Invariant Split Point Walk in your language of choice

File: solution.py
Python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def lowest_common_ancestor(root: TreeNode | None, p: TreeNode, q: TreeNode) -> TreeNode | None:
    curr = root
    while curr:
        if p.val < curr.val and q.val < curr.val:
            curr = curr.left
        elif p.val > curr.val and q.val > curr.val:
            curr = curr.right
        else:
            return curr
    return None
if __name__ == "__main__":
    # Tree: [6, 2, 8, 0, 4, 7, 9]
    root = TreeNode(6)
    root.left = TreeNode(2, TreeNode(0), TreeNode(4))
    root.right = TreeNode(8, TreeNode(7), TreeNode(9))
    p = root.left       # node 2
    q = root.right      # node 8
    lca = lowest_common_ancestor(root, p, q)
    print("LCA value:", lca.val if lca else "None")
Interactive visualizer available

Understand Binary Search Tree Visually

Explore hierarchical parent-child nodes, traversal modes (in-order, pre-order, post-order), and search lookups. Test live edge cases and watch memory state transitions step-by-step.

Launch Binary Search Tree Visualizer

Frequently Asked Questions

Related Logic & Algorithm Problems

All problems
EasyTrees & BST
Visualizer

Maximum Depth of Binary Tree

Find the maximum depth (height) of a binary tree along the longest path from root to leaf. The quintessential problem for learning bottom-up divide-and-conquer tree recursion.

1 approach(O(n))
Learn logic
EasyTrees & BST
Visualizer

Invert Binary Tree

Mirror-flip a binary tree so every left subtree swaps with the right subtree. The quintessential problem for mastering tree recursion and depth-first traversal.

1 approach(O(n))
Learn logic
EasyTrees & BST
Visualizer

Subtree of Another Tree

Determine if a binary tree contains a subtree identical in structure and node values to another tree. Learn how to combine outer tree DFS traversal with inner tree isomorphism matching.

1 approach(O(n * m))
Learn logic