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 approach to traverse the tree.
2. Base Cases:
   • If the current node is null, return null.
   • If the current node is either p or q, return the current node.
3. Recursive Calls: Recursively call the function for the left and right subtrees.
4. Check Results:
   • If both left and right recursive calls return a node (meaning both p and q are found in different subtrees), then the current node is the LCA. Return the current node.
   • If only one of the recursive calls returns a node, that node is the LCA (either p or q is a descendant of the current node). Return the non-null result.
   • If both recursive calls return null, then neither p nor q are in the current subtree. Return null.

Explanation

The recursive approach efficiently explores the tree. By checking the results of the recursive calls on the left and right subtrees, we can determine if the current node is the LCA. If both p and q are found in different subtrees, the current node must be their LCA. If only one is found in a subtree, then the found node itself is the LCA. If neither are found, the LCA is not in this subtree.

Code

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val===undefined ? 0 : val)
        this.left = (left===undefined ? null : left)
        this.right = (right===undefined ? null : right)
    }
}

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
    if (!root || root === p || root === q) return root;

    const left = lowestCommonAncestor(root.left, p, q);
    const right = lowestCommonAncestor(root.right, p, q);

    if (left && right) return root; // p and q are in different subtrees
    return left || right; // p or q is in one subtree
};

Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. In the worst case, we might visit every node once.
• 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 is log(N).