[LeetCode] 236. Lowest Common Ancestor of a Binary Tree

Problem

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).”

BCR(Best Conceivable Runtime)

To find the lowest common ancestor, we need to find which the node is p or q at first, So the BCR is $O(N)$, which $N$ is the number of the node in the tree.

Solution

There are two cases of this problem. The first case is that we find p and q at the different subtree (for example, p = 6, q = 0) and the second case is that we find p and q at the same subtree (for example, p = 5, q = 7 or p = 2, q = 4).

In the first case, if p is in the left subtree of some node and q is in the right subtree of the node, then the node is the lowest common ancestor of p and q.

In the second case, if we found either p or q in the subtree and we can't find the other node at the opposite subtree, it is clear that the other node is in the subtree where we found the node so the node we found is the lowest common ancestor.

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;
        return left != null ? left : right;
    }
}

The time complexity is $O(N)$, which $N$ is the number of the node and the space complexity is $O(N$) too, because of recursion.