Lowest Common Ancestor of a Binary Tree II

Link

Description

Given the root of a binary tree, return the lowest common ancestor (LCA) of two given nodes, p and q. If either node p or q does not exist in the tree, return null. All values of the nodes in the tree are unique.

According to the definition of LCA on Wikipedia: "The lowest common ancestor of two nodes p and q in a binary tree T is the lowest node that has both p and q as descendants (where we allow a node to be a descendant of itself)". A descendant of a node x is a node y that is on the path from node x to some leaf node.

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. A node can be a descendant of itself according to the definition of LCA.

Example 3:

• Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 10
• Output: null
• Explanation: Node 10 does not exist in the tree, so return null.

Constraints:

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

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 {
private:
    TreeNode* lowestCommonAncestorOriginal(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root || root == p || root == q) return root;

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

        if (left && right) return root;

        return left ? left : right;
    }

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

        auto res = lowestCommonAncestorOriginal(root, p, q);
        if (res == p) {
            return lowestCommonAncestorOriginal(p, q, q) ? res : nullptr;
        } else if (res == q) {
            return lowestCommonAncestorOriginal(q, p, p) ? res : nullptr;
        }

        return res;
    }
};

This original solution for Leetcode 236 doesn't account for the cases where p or q are not in the binary tree. In that solution, the stopping condition for the recursion is if root == None or root == p or root == q, then return root. This means if we encounter p, we won't explore the subtree as we immediately return. If q does not exist in the subtree of p, we will never know. For this case, the method will return p and q respectively, which is incorrect as we should be returning null instead.

If this method returns p as the lowest common ancestor, we can check for q in the subtree of p to ensure that both the nodes are present. Likewise, for the case where this method returns q as the lowest common ancestor we can check for p in the subtree of q to ensure that both nodes are present. If this method returns null, it indicates that neither p nor q are present in the tree.

• Time complexity: \(O(N)\);
• Space complexity: \(O(N)\).