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.

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, it means one target node was found in each subtree. Therefore, the current node is 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 indicating neither p nor q were found in this subtree.

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 Considering a Node as Its Own Ancestor:
  Failing to return the node when it matches p or q might result in an incorrect LCA.

• Incorrect Recursion Logic:
  Not properly checking both left and right subtrees can cause missed intersections.

Edge Cases

• One Node is Ancestor of the Other:
  For instance, if p is an ancestor of q, the LCA should be p.

• 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 LCA can be found more efficiently using the properties of BST ordering.

• LCA with Parent Pointers:
  If each node has a pointer to its parent, the problem can be solved by iterating upwards from the nodes.

Related Problems for Further Practice

• Lowest Common Ancestor of a Binary Search Tree:
  A simplified version that leverages BST properties.

• Distance Between Two Nodes in a Binary Tree:
  Find the distance (number of edges) between two given nodes using the LCA.