Find the Lowest Common Ancestor Node from a Binary Tree with two given nodes

What is Lowest Common Ancestor or [LCA] in a Binary Tree?

Picture is worth thousand words, from the Binary Tree given below.

LCA[10, 14] = 15

LCA[10, 12] = 12

LCA[14, 19] = 15

LCA[12, 15] = 15

The essential observation is the intersection of two paths from the root to each node

It might be useful to ask slightly different question.

Given a number, and find the node that contains the number

e.g. Node findNode[Node root, int number]

Algorithm

To start from the top, if root equals to the number, then return the root node.

Otherwise, recur to left subtree and right subtree.

If the referene[s] from left subtree and right subtree are both not null, then return the root node

Otherwise return the reference that is not null from one of the subtree

Picture is worth thousand words, from the Binary Tree given below.

LCA[10, 14] = 15

LCA[10, 12] = 12

LCA[14, 19] = 15

LCA[12, 15] = 15

The essential observation is the intersection of two paths from the root to each node

It might be useful to ask slightly different question.

Given a number, and find the node that contains the number

e.g. Node findNode[Node root, int number]

Algorithm

To start from the top, if root equals to the number, then return the root node.

Otherwise, recur to left subtree and right subtree.

If the referene[s] from left subtree and right subtree are both not null, then return the root node

Otherwise return the reference that is not null from one of the subtree

```
public static Node findNode(Node root, int n){
if(root != null){
if( root.data == n)
return root;
Node l = findNode(root.left, n);
Node r = findNode(root.right, n);
if(l != null)
return l;
else if(r != null)
return r;
}
return null;
}
```

Now we can slightly modify the findNode method and solve the LCA problem

Instead of looking for one node, we can look for two nodes from the findNode method.

We change the findNode name to LCA from now on since we are working on LCA problem.

Instead of looking for one node, we can look for two nodes from the findNode method.

We change the findNode name to LCA from now on since we are working on LCA problem.

Node LCA(Node r, int n1, int n2){ if(r != null){ if(r.data == n1 || r.data == n2){ return r; Node left = LCA(r.left, n1, n2); Node right = LCA(r.right, n1, n2); if(left != null) return left; if(right != null) return right; } }

The above code essentially means if one of the node is found from the Binary Tree,

then return the reference to its parent, otherwise return null

what happen if left and right are both not null, then the current node is essentially

the intersection of two paths which are from the root to the two given number associated with its node

then return the reference to its parent, otherwise return null

what happen if left and right are both not null, then the current node is essentially

the intersection of two paths which are from the root to the two given number associated with its node

```
public static Node LCA_BasedOnFindNode(Node r, int n1, int n2){
if(r != null){
if(r.data == n1 || r.data == n2)
return r;
Node left = LCA_BasedOnFindNode(r.left, n1, n2);
Node right = LCA_BasedOnFindNode(r.right, n1, n2);
if(left != null && right != null)
return r;
else if(left != null)
return left;
else if(right != null)
return right;
}
return null;
}
```