Lowest Common Ancestor of a Binary Tree

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

The lowest common ancestor is defined as the deepest node that is an ancestor of both p and q. A node can be an ancestor of itself.

Function signature

func LowestCommonAncestor(root, p, q *TreeNode) *TreeNode

TreeNode definition

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

Examples

Example 1:

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

p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

Input: Same tree as above
p = 5, q = 4
Output: 5
Explanation: The LCA of 5 and 4 is 5, since a node can be an ancestor of itself.

Example 3:

Input: Same tree as above
p = 6, q = 4
Output: 5
Explanation: Node 5 is the deepest node that is an ancestor of both 6 and 4.

Example 4:

Input:
  1
 /
2

p = 1, q = 2
Output: 1

Constraints

• The number of nodes in the tree is in the range [2, 10000]
• All node values are unique
• p and q are different nodes and both exist in the tree

Hints

1. If the current node is p or q, what should you return?
2. After checking left and right subtrees, what does it mean if both return non-null?
3. What if only one subtree returns non-null?

Notes

• This is a subtle recursion problem. The key insight is that when both left and right subtrees return non-null results, the current node must be the LCA.
• Don't confuse this with LCA in a BST, which can use the BST property to search more efficiently.