Lowest Common Ancestor of a Binary Tree

Link

Description

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.

Example 3:

• Input: root = [1,2], p = 1, q = 2
• Output: 1

Constraints:

• The number of nodes in the tree is in the range [2, 10^5].
• -10^9 <= Node.val <= 10^9
• All Node.val are unique.
• p != q
• p and q will exist in the tree.

Solution

Recursive Solution

/**
 * 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) return nullptr;
        if (root == p || root == q) return root;

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

        if (left && right) return root;
        if (!left && !right) return nullptr;

        return left ? left : right;
    }
};

Simplified version (See reference (Chinese)):

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root || root == p || root == q) return root;

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

        if (left && right) return root;
        return left ? left : right;
    }
};

The main idea behind the algorithm is to recursively search for the two nodes (p and q) starting from the root. During the recursion, any node can be in one of the three states:

1. The node itself is one of the targets (p or q).
2. The node is an ancestor of one of the targets, which means one of the targets is located in its left or right subtree.
3. The node is the lowest common ancestor (LCA), which means one target is in its left subtree, and the other is in its right subtree.

Steps:

1. Base Case: If the current node is nullptr, we return nullptr, indicating that neither p nor q was found in the current path.

2. Check Current Node: If the current node is either p or q, return the current node. This means we have found one of the two nodes we're looking for.

3. Divide: Recursively call the function for the left and right children of the current node.

   • left will contain the result of the LCA search in the left subtree.
   • right will contain the result of the LCA search in the right subtree.

4. Conquer:

   • If both left and right are non-null, it means we have found both p and q in different subtrees of the current node. Hence, the current node is their LCA.
   • If both left and right are null, it means neither p nor q was found in the subtrees of the current node. Return nullptr.
   • If one of left or right is non-null, return the non-null one. This means we have found either p or q (but not both) in one of the subtrees.

Time Complexity:

The time complexity of this algorithm is \(O(N)\), where \(N\) is the number of nodes in the binary tree. This is because, in the worst case, the algorithm needs to visit each node exactly once to check if it's either of the nodes we're looking for or if it's their lowest common ancestor.

Space Complexity:

The space complexity of the algorithm is \(O(H)\), where \(H\) is the height of the binary tree. This space is used by the call stack during the recursion. In the worst case, for a skewed binary tree, the height of the tree can become \(N\) (where the tree is essentially a linked list), making the space complexity \(O(N)\). For a balanced tree, the space complexity would be \(O(\log N)\), where \(\log N\) is the height of the tree.

Iterative Solution

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        stack<TreeNode*> stk;  // Stack for tree traversal
        unordered_map<TreeNode*, TreeNode*> parent;  // HashMap for parent pointers
        unordered_set<TreeNode*> ancestors;  // Ancestors set for node p

        parent[root] = nullptr;
        stk.push(root);

        // Iterate until we find both the nodes p and q
        while (parent.find(p) == parent.end() || parent.find(q) == parent.end()) {
            auto node = stk.top();
            stk.pop();

            // While traversing the tree, keep saving the parent pointers
            if (node->left) {
                parent[node->left] = node;
                stk.push(node->left);
            }
            if (node->right) {
                parent[node->right] = node;
                stk.push(node->right);
            }
        }

        while (p) {  // Process all ancestors for node p using parent pointers
            ancestors.insert(p);
            p = parent[p];
        }

        // The first ancestor of q which appears in
        // p's ancestor set is their lowest common ancestor
        while (ancestors.find(q) == ancestors.end()) {
            q = parent[q];
        }

        return q;
    }
};

Approach Explanation:

• Start from the root node and traverse the tree.
• Until we find p and q both, keep storing the parent pointers in a dictionary.
• Once we have found both p and q, we get all the ancestors for p using the parent dictionary and add to a set called ancestors.
• Similarly, we traverse through ancestors for node q. If the ancestor is present in the ancestors set for p, this means this is the first ancestor common between p and q (while traversing upwards) and hence this is the LCA node.