236. Lowest Common Ancestor of a Binary Tree - Detailed Explanation

Problem statement

Given the root of a binary tree and two nodes p and q in the tree, find the lowest common ancestor (LCA) of p and q.

Definition of lowest common ancestor: The lowest common ancestor of two nodes p and q is defined as the lowest node in the tree that has both p and q as descendants (where we allow a node to be a descendant of itself).

Example 1:

Consider the following binary tree:

         3
        / \
       5   1
      / \  / \
     6  2 0   8
       / \
      7   4

• Input: root = 3, p = 5, q = 1
• Output: 3
• Explanation: The LCA of nodes 5 and 1 is 3 since 3 is the lowest node that has both nodes as descendants.

Example 2:

• Input: root = 3, p = 5, q = 4
• Output: 5
• Explanation: The LCA of nodes 5 and 4 is 5 since a node can be a descendant of itself.

This question is an instance of the tree depth first search pattern, in which a recursive call descends to the leaves and each node combines what its two children reported. No extra data structure is needed, because the recursion stack already records the path from the root. The most common LeetCode patterns summary shows where tree depth first search sits among the other techniques, and Grokking the Coding Interview teaches the pattern with graded practice problems.

Hints

• Hint 1: Use a depth-first search (DFS) traversal. The idea is to recursively search the left and right subtrees for p and q.

• Hint 2: When the recursive call returns non-null values from both the left and right subtrees, one target node was found in each subtree. The current node is therefore the lowest common ancestor.

Approaches

Approach 1: recursive depth-first search (DFS)

Explanation

1. Base case: If the current node is null or equals p or q, return the current node. This signals that one of the target nodes has been found, or that the branch is exhausted.

2. Recursive search:

   • Recursively search in the left subtree.
   • Recursively search in the right subtree.

3. Determining the LCA:

   • Both left and right calls return non-null: This means p was found in one subtree and q in the other. The current node is the LCA.
   • Only one of them is non-null: Return the non-null value, which means both p and q are located in that subtree.
   • Both are null: Return null, which indicates that neither p nor q was found in this subtree.

Each node decides after both children have answered, so the deepest node that sees a target on each side reports itself. Every ancestor above it then receives one non-null value and passes that same node upward unchanged.

Pseudocode

function lowestCommonAncestor(root, p, q):
    if root is null or root equals p or root equals q:
        return root

    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)

    if left is not null and right is not null:
        return root

    return left if left is not null else right

Code examples

Python code

Complexity analysis

• Time complexity:

  • In the worst case, every node in the tree is visited once.
  • Overall: O(N), where N is the number of nodes in the tree.

• Space complexity:

  • The space complexity is determined by the recursion stack. In the worst case, a skewed tree, the stack depth could be O(N).
  • On average, for a balanced tree, the stack depth is O(log N).

Common mistakes and edge cases

Common mistakes

• Not treating a node as its own ancestor: Failing to return the node when it matches p or q produces an incorrect LCA. Example 2 depends on that return.

• Incorrect recursion logic: Checking only one subtree, or returning early before both children answer, causes missed intersections.

Edge cases

• One node is an ancestor of the other: If p is an ancestor of q, the LCA is p. The base case returns p before the recursion ever reaches q.

• Null tree: If the tree is empty, the function should return null.

Alternative variations and related problems

Variations

• LCA in a binary search tree (BST): In a BST, the ordering of the keys locates the LCA without searching both subtrees. That version appears on the Blind 75 list.

• LCA with parent pointers: If each node has a pointer to its parent, you can solve the problem by walking upward from the two nodes.

Related problems for further practice

• Lowest Common Ancestor of a Binary Search Tree: A simpler version that uses the BST ordering property.

• Distance Between Two Nodes in a Binary Tree: Find the distance, measured in edges, between two given nodes using the LCA.

Both questions reuse the same recursive descent, so the pattern is worth learning once and applying often. The recurring LeetCode patterns post covers tree depth first search along with the other techniques that interviewers repeat.