1650.md

1650. Lowest Common Ancestor of a Binary Tree III

Level:

Topic:

Similar Problem:

• 160. Intersection of Two Linked Lists
• 235. Lowest Common Ancestor of a Binary Search Tree
• 236. Lowest Common Ancestor of a Binary Tree
• 1644. Lowest Common Ancestor of a Binary Tree II

Question

Given two nodes of a binary tree p and q, return their lowest common ancestor (LCA).

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

Iterative:

Given only the node at p and q, but not root of the tree. And every node we can get its parent node.

1. while two nodes intersect, it's the lowest common ancestor
2. similar to 160, if either became null (means reaching the root node) switch to the other starting node

Code

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

Iterative

public Node lowestCommonAncestor(Node p, Node q) {
    Node a = p, b = q;
    while (a != b) {
        a = a == null ? q:a.parent;
        b = b == null ? p:b.parent;
    }
    return a;
}