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 employ a recursive approach to traverse the binary tree.
2. Base Cases:
   • If the current node is null, it means we haven't found either p or q, so we return null.
   • If the current node is equal to either p or q, we've found one of the nodes, so we return the current node.
3. Recursive Calls: We recursively call the function on the left and right subtrees.
4. Result Combination:
   • If both recursive calls return a non-null value, it means that p and q are present in both subtrees, and the current node is their LCA. We return the current node.
   • If only one recursive call returns a non-null value, it means that one of the nodes is in one of the subtrees, and the current node is on the path to that node. We return the non-null result.
   • If both recursive calls return null, it means neither p nor q are present in the current subtree, so we return null.

Explanation

The recursive approach cleverly leverages the tree's structure. By checking if the current node is p or q, and then recursively exploring both subtrees, we effectively search for both nodes simultaneously. The logic for combining the results from the recursive calls ensures that we find the lowest common ancestor. 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, the current node is on the path to that node, and we continue searching up the tree.

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }

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

        if (left != null && right != null) {
            return root;
        } else if (left != null) {
            return left;
        } else {
            return right;
        }
    }
}

Complexity

• Time Complexity: O(N), where N is the number of nodes in the binary tree. In the worst case, we might visit each node once.
• Space Complexity: O(H), where H is the height of the binary tree. This is due to the recursive call stack. In the worst case (a skewed tree), H could be equal to N. In a balanced tree, H is log(N).