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 employ a recursive approach that traverses the tree.
2. Base Cases:
   • If the current node is nullptr, we return nullptr.
   • If the current node is either p or q, we return the current node.
3. Recursive Calls: We recursively search for p and q in the left and right subtrees.
4. LCA Found:
   • If both recursive calls from the left and right subtrees return non-nullptr values, 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-nullptr value, it means that one of p or q is in one of the subtrees, and we return the non-nullptr result.
   • If both recursive calls return nullptr, it means neither p nor q is in the current subtree, so we return nullptr.

Explanation

The algorithm works because it systematically explores the tree. If p and q are in different subtrees of a node, that node must be their LCA. If they are both in the same subtree, the LCA will be found deeper in that subtree. The base cases handle the scenarios where we reach the end of a branch or find one of the target nodes.

Code

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

        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);

        if (left && right) {
            return root;
        } else if (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 visit each 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.