Lowest Common Ancestor of a Binary Tree

Problem Description
Given a binary tree and two nodes p and q, find their lowest common ancestor (LCA) in the tree. The definition of the lowest common ancestor is: For two nodes p and q in a rooted tree T, the lowest common ancestor is a node x such that x is an ancestor of both p and q, and the depth of x is as large as possible (a node can be an ancestor of itself).

Solution Process

1. Understanding the Problem and Examples
   First, we need to clarify the meaning of "common ancestor." Suppose we have a binary tree:

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

   If p is node 5 and q is node 1, their lowest common ancestor is the root node 3.
   If p is node 5 and q is node 4, their lowest common ancestor is node 5 (since node 5 is an ancestor of node 4).

2. Analyzing Problem Characteristics
   The lowest common ancestor (LCA) problem can be solved either recursively or iteratively. The recursive approach is more intuitive. Its core idea is:

   • Traverse the binary tree starting from the root.
   • If the current node is p or q, return the current node.
   • If p and q are located in the left and right subtrees of the current node, respectively, then the current node is the LCA.
   • If both p and q are in the left subtree, continue searching in the left subtree; similarly, if both are in the right subtree, search in the right subtree.

3. Recursive Solution Steps

   • Termination Condition: If the current node is null, or the current node is p or q, return the current node.
   • Recursively Traverse Left and Right Subtrees: Call the recursive function on the left child and right child, respectively.
   • Evaluate Results:
     • If the result from the left subtree is null, it means both p and q are in the right subtree; return the result from the right subtree.
     • If the result from the right subtree is null, it means both p and q are in the left subtree; return the result from the left subtree.
     • If the results from both left and right subtrees are not null, it means p and q are located on opposite sides of the current node, and the current node is the LCA; return the current node.

4. Code Implementation (Recursive)

   def lowestCommonAncestor(root, p, q):
       if not root or root == p or root == q:
           return root
       left = lowestCommonAncestor(root.left, p, q)
       right = lowestCommonAncestor(root.right, p, q)
       if not left:
           return right
       if not right:
           return left
       return root
   

5. Complexity Analysis

   • Time Complexity: O(n), where n is the number of nodes in the binary tree. In the worst case, all nodes need to be traversed.
   • Space Complexity: O(h), where h is the height of the tree. The depth of the recursion stack depends on the height of the tree.

6. Extended Considerations
   If the binary tree in the problem is a Binary Search Tree (BST), we can simplify the problem using the properties of a BST (all node values in the left subtree are less than the root node, and all node values in the right subtree are greater than the root node):

   • If the values of both p and q are less than the current node's value, the LCA is in the left subtree.
   • If the values of both p and q are greater than the current node's value, the LCA is in the right subtree.
   • Otherwise, the current node is the LCA.