# 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