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

Example:

Code:

Explanation:

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

Github link to the solution:

https://github.com/shivanidwivedi/JavaProgramming/commit/e02cd98c0384b222f10a9feb4a49f9ff8f60adea