Lowest Common Ancestor

Description

Given a binary tree root, and integers a and b, find the value of the lowest node that has a and b as descendants. A node can be a descendant of itself.

All nodes in the tree are guaranteed to be unique.

Constraints:

• n ≤ 100,000 where n is the number of nodes in root

Example 1

Input

root = [0, [1, null, null], [2, [6, [3, null, null], [4, null, null]], [5, null, null]]]
a = 3
b = 5

Output

2

---

Example 2

Input

root = [0, [1, null, null], [2, [6, [3, null, null], [4, null, null]], [5, null, null]]]
a = 6
b = 4

Output

6

---

Intuition

DFS

1. root == null, return null;
2. root == a or b, return root;
3. if root.left != null & root.right != null, return root, which is answer;
4. if root.left != null || root.right !=null, return left or right

Implementation

import java.util.*;

/**
 * public class Tree {
 *   int val;
 *   Tree left;
 *   Tree right;
 * }
 */
class Solution {
    public int solve(Tree root, int a, int b) {
        return lca(root, a, b).val;
    }

    private Tree lca(Tree root, int a, int b) {
        if (root == null) {
            return null;
        }
        if (root.val == a || root.val == b) {
            return root;
        }
        Tree left = lca(root.left, a, b);
        Tree right = lca(root.right, a, b);
        if (left != null && right != null) {
            return root;
        } else if (left != null) {
            return left;
        } else if (right != null) {
            return right;
        } else {
            return null;
        }
    }
}

Time Complexity

• Time: O(n)
• Space: O(logn)