235. Lowest Common Ancestor of a Binary Search Tree

How to solve Lowest Common Ancestor of a Binary Search Tree (LeetCode 235): the approach in brief

The problem

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

Pattern

Lowest Common Ancestor of a Binary Search Tree is a Tree Traversal Patterns (DFS & BFS) problem, in the Lowest Common Ancestor (LCA) Finding subpattern. The pattern covers preorder, inorder, level order traversal, LCA, and serialization

Find lowest common ancestor in binary trees and BSTs using recursive and iterative approaches.

Approach outline

1. Recall that a Binary Search Tree (BST) has the property where the left child is smaller and the right child is larger than the parent node.
2. Since the tree is a BST, consider how the values of the two nodes p and q relate to the current node's value to guide your traversal direction.
3. Think about traversing the tree starting from the root and deciding whether to go left, right, or stop based on the values of p, q, and the current node.

Complexity

The reference solution runs in O(h) time and O(n) space.

Asked at

Lowest Common Ancestor of a Binary Search Tree has been reported in interviews at Amazon, Facebook, LinkedIn, Oracle, Microsoft.