Lowest Common Ancestor of a Binary Tree medium

Problem Statement

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

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: 3 Explanation: The LCA of nodes 5 and 1 is 3.

Example 2

Input: root = [3,5,1,6,2,0,8,null,null,7,4], 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 according to the LCA definition.

Steps

1. Recursive Approach: We'll use a recursive function to traverse the tree.
2. Base Cases:
   • If the current node is None, return None.
   • If the current node is either p or q, return the current node.
3. Recursive Calls: Recursively call the function on the left and right subtrees.
4. Check Results:
   • If both recursive calls return a node (meaning both p and q are found in the subtrees), the current node is the LCA. Return the current node.
   • If only one recursive call returns a node, return that node (it's the path to one of p or q).
   • If both recursive calls return None, return None.

Explanation

The algorithm leverages the recursive nature of a tree traversal. By checking if either p or q is the current node, and then recursively searching the left and right subtrees, we effectively explore all paths from the root to p and q. The crucial part is the check after the recursive calls: If both left and right subtrees return a node, it means p and q are on different branches below the current node, making the current node their LCA. If only one subtree returns a node, that node is on the path to one of p or q, and it is further up the tree than the LCA. If both subtrees return None, neither p nor q is found in the current subtree.

Code

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

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or root == p or root == q:
            return root

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

        if left and right:
            return root
        elif left:
            return left
        else:
            return right

Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. In the worst case, we might traverse the entire tree.
• Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H can be equal to N. In a balanced tree, H would be log N.