1644.md

1644. Lowest Common Ancestor of a Binary Tree II

Level:

Topic:

Similar Problem:

• 235. Lowest Common Ancestor of a Binary Search Tree
• 236. Lowest Common Ancestor of a Binary Tree
• 1650. Lowest Common Ancestor of a Binary Tree III

Question

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.

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.\

Intuition

See Comments

Code

Time: O(n)
Space: O(n)

Recursive

// p and/or q might not be in the tree
// so the lca is found iff both p and q are in the tree
boolean foundP = false, foundQ = false;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    TreeNode lca = helper(root, p, q);
    if (foundP && foundQ)
        return lca;
    return null;
}
private TreeNode helper(TreeNode root, TreeNode p, TreeNode q) {
    // base case for traversal
    if (root == null)
        return null;

    // since it's looking for the ancestor,
    // need to search in the lower level
    // if there exists both path,
    // return the root which is the lca
    TreeNode left = helper(root.left, p, q);
    TreeNode right = helper(root.right, p, q);

    // mark the boolean if p or q is found
    // so there is a path found and return back up
    // even if the current node is p or q,
    // we still need to search for the other,
    // since one can be the ancestor of the other
    if (root == p) {
        foundP = true;
        return root;
    }
    else if (root == q) {
        foundQ = true;
        return root;
    }
    // 2 cases:
    // 1. two paths are found, then lca is found
    if (left != null && right != null)
        return root;

    // 2. if two both path are null, we don't
    // need to search
    else if (left == null && right == null)
        return null;

    // 3 & 4. either one path is found
    // mean the null path will never exist a path
    // for the other node
    return left == null ? right : left;
}