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;
}