Java: Lowest Common Ancestor of a Binary Tree

Problem Statement: Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

LCA is defined between two nodes p and q as the lowest node in the tree that has both p and q as descendants (where a node can be a descendant to itself).




Above is the iterative approach to the problem.

Starting from the root node, we need to maintain HashMap to store the parent pointers of each node until we find both p and q (for the root node, keep null as the parent pointer).

Once we found p and q, we need to keep all the ancestors of p from the Hashmap in a set(ancestor). Similarly, we need to find all the ancestors of q and check if it is present in the ancestor set of p. If present, it means it is the first LCA between p and q while going upwards.

Complexity Analysis:

Time Complexity: O(N), N is the number of nodes in the binary tree. We might visit all the nodes in the worst case.

Space Complexity: O(N).