Lowest Common Ancestor of a Binary Tree - Python Solution

1. Introduction

The "Lowest Common Ancestor of a Binary Tree" problem is a classic question in binary tree algorithms. It involves finding the lowest common ancestor (LCA) of two nodes in a binary tree, which is the lowest node that has both nodes as descendants. This problem is essential for understanding tree traversal and recursion in tree data structures.

Problem

Given a binary tree, the task is to find the lowest common ancestor (LCA) of two given nodes in the tree. According to the definition, the LCA is the lowest node in the tree that has both nodes as descendants, where a node can be a descendant of itself.

2. Solution Steps

1. Implement a recursive function to traverse the tree and find the LCA.

2. If either of the given nodes matches the current node, return the current node.

3. Recursively search for the nodes in the left and right subtrees.

4. If both subtrees return a non-null value, the current node is the LCA.

5. If only one subtree returns a non-null value, return that value.

6. If both subtrees return null, return null.

3. Code Program

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

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 left and right:
        return root
    return left if left else right

# Example Usage
root = TreeNode(3)
root.left = TreeNode(5, TreeNode(6), TreeNode(2, TreeNode(7), TreeNode(4)))
root.right = TreeNode(1, TreeNode(0), TreeNode(8))
p = root.left  # Node 5
q = root.right  # Node 1
print(lowestCommonAncestor(root, p, q).val)

Output:

3

Explanation:

1. Recursive Search: The function lowestCommonAncestor searches the tree recursively for the given nodes p and q.

2. Base Case: If the current node is one of the nodes p or q, or if it is null, it returns the current node.

3. Left and Right Traversal: The function explores both the left and right subtrees to look for nodes p and q.

4. LCA Determination: If both left and right subtree calls return non-null, the current node is the LCA.

5. Subtree Result: If only one subtree returns a non-null node, that node is the LCA.

6. LCA Result: The function returns the lowest common ancestor node of p and q.