236. Lowest Common Ancestor of a Binary Tree

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

The problem

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

Pattern

Lowest Common Ancestor of a Binary 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. Consider using a tree traversal technique like Depth-First Search (DFS) to explore nodes systematically.
2. Think about how recursion can help you check whether the current node is an ancestor of either target node.
3. When traversing, determine if the current node matches either target node or if those nodes are found in different subtrees.

Complexity

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

Asked at

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