# Lowest Common Ancestor of a Binary Tree

Medium

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

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:

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

Example 2:

``````Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.``````

Constraints:

• The number of nodes in the tree is in the range `[2, 105]`.
• `-109 <= Node.val <= 109`
• All `Node.val` are unique.
• `p != q`
• `p` and `q` will exist in the tree.

#### Iterative using parent pointers

Intuition

If we have parent pointers for each node we can traverse back from `p` and `q` to get their ancestors. The first common node we get during this traversal would be the LCA node. We can save the parent pointers in a dictionary as we traverse the tree.

Algorithm

1. Start from the root node and traverse the tree.
2. Until we find `p` and `q` both, keep storing the parent pointers in a dictionary.
3. Once we have found both `p` and `q`, we get all the ancestors for `p` using the parent dictionary and add to a set called `ancestors`.
4. Similarly, we traverse through ancestors for node `q`. If the ancestor is present in the ancestors set for `p`, this means this is the first ancestor common between `p` and `q` (while traversing upwards) and hence this is the LCA node.
```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

if(root == null){
return root;
}
if(p == null){
return q;
}
if(q == null){
return p;
}
Map<TreeNode, TreeNode> parentMap = new HashMap<>();
parentMap.put(root, null);
populateParentMap(parentMap, root);
Set<TreeNode> visited = new HashSet<>();
while(p != null){
p = parentMap.get(p);
}
TreeNode lca = null;
while(q != null){
if(visited.contains(q)){
lca = q;
break;
}
q = parentMap.get(q);
}
return lca;
}

private void populateParentMap(Map<TreeNode, TreeNode> parentMap, TreeNode node){
if(node == null){
return;
}
TreeNode leftChild = node.left;
TreeNode rightChild = node.right;
if(leftChild != null){
parentMap.put(leftChild, node);
}
if(rightChild != null){
parentMap.put(rightChild, node);
}
populateParentMap(parentMap, leftChild);
populateParentMap(parentMap, rightChild);
}
}
```

Complexity Analysis

• Time Complexity : O(N), where N is the number of nodes in the binary tree. In the worst case we might be visiting all the nodes of the binary tree.
• Space Complexity : O(N). In the worst case space utilized by the stack, the parent pointer dictionary and the ancestor set, would be N each, since the height of a skewed binary tree could be N.

Categories: Binary Tree

Tagged as: ,