#236

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Lowest Common Ancestor of a Binary Tree

Identify the lowest common ancestor of two nodes in a binary tree using traversal and state tracking techniques efficiently.

tree depth first search binary tree

Problem Statement

Given a binary tree and two distinct nodes p and q, determine their lowest common ancestor (LCA). The LCA is defined as the lowest node in the tree that has both p and q as descendants, where a node can be a descendant of itself.

For example, consider root = [3,5,1,6,2,0,8,null,null,7,4]. If p = 5 and q = 1, the LCA is 3. If p = 5 and q = 4, the LCA is 5. Return the value of the LCA node for the given inputs.

Examples

Example 1

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

Output: 3

The LCA of nodes 5 and 1 is 3.

Example 2

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

Output: 5

The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Example 3

Input: root = [1,2], p = 1, q = 2

Output: 1

Example details omitted.

Constraints

The number of nodes in the tree is in the range [2, 105].
-109 <= Node.val <= 109
All Node.val are unique.
p != q
p and q will exist in the tree.

Solution Approach

Recursive DFS with backtracking

Traverse the tree recursively and return the node itself if it matches p or q. Propagate non-null returns from left and right children, and identify the first node with both sides non-null as the LCA.

Parent mapping with set tracking

Use a DFS to map each node to its parent, then build ancestor sets for p and q. Traverse ancestors of one node to find the first common node in the other's ancestor path.

Iterative DFS using a stack

Maintain a stack for tree traversal and a parent dictionary to track parent nodes. After locating both nodes, iterate upward to determine the lowest node present in both ancestor paths.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) in all approaches, where n is the number of nodes, because each node is visited once. Space complexity is O(h) for recursion stack or O(n) for parent mapping, with h being the tree height.

What Interviewers Usually Probe

Check whether your solution handles one node being the ancestor of the other.
Ensure you efficiently track state without redundant traversals to meet O(n) time.
Consider whether recursive backtracking or parent mapping aligns better with memory constraints.

Common Pitfalls or Variants

Common pitfalls

Failing to account for a node being a descendant of itself can return incorrect LCA.
Overlooking null child nodes when propagating results may cause wrong merges in DFS.
Confusing iterative parent tracking with naive BFS can increase space usage unnecessarily.

Follow-up variants

Finding LCA in a Binary Search Tree allows value comparisons to prune subtrees.
Determine LCA when nodes may not exist, requiring additional existence checks.
Find LCA for multiple pairs of nodes efficiently using a single traversal with preprocessing.

FAQ

What is the best method to find the lowest common ancestor in a binary tree?

Recursive DFS with backtracking is generally simplest and efficient, ensuring O(n) time and handling cases where one node is ancestor of the other.

Can a node be the lowest common ancestor of itself?

Yes, according to the LCA definition, a node can be a descendant of itself, which is crucial when one target node is the ancestor of the other.

How does the parent mapping approach work for LCA?

It tracks each node's parent during DFS, then constructs ancestor paths for both nodes to find their first intersection, identifying the LCA.

What are common mistakes when implementing LCA solutions?

Ignoring null checks, mismanaging recursive return values, or forgetting that nodes can be their own ancestor can lead to wrong answers.

Is there a difference between LCA in a binary tree versus a binary search tree?

Yes, in a BST you can leverage value comparisons to prune traversal, which is faster than generic DFS used in ordinary binary trees.

terminal

Solution

Solution 1: Recursion

We recursively traverse the binary tree:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution:
    def lowestCommonAncestor(
        self, root: "TreeNode", p: "TreeNode", q: "TreeNode"
    ) -> "TreeNode":
        if root in (None, p, q):
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        return root if left and right else (left or right)

Continue Practicing

#235 lowest common ancestor of a binary search tree #230 kth smallest element in a bst #226 invert binary tree