## Tuesday, March 27, 2018

### Find Longest Common Ancestor(LCA) Program in java

Objective : The objective of this problem is to find the Longest Common Ancestor of the Tree.

Longest Common Ancestor is the common node in a tree who is common among the given 2 or more node.

Implementation :

```import java.util.HashMap;
import java.util.Stack;

public class LCA {
public static void main(String[] args) {
// NOTE: The following input values will be used for testing your solution.
// The mapping we're going to use for constructing a tree.
// For example, {0: [1, 2]} means that 0's left child is 1, and its right
// child is 2.
HashMap<Integer, int[]> mapping1 = new HashMap<Integer, int[]>();
int[] childrenA = {1, 2};
int[] childrenB = {3, 4};
int[] childrenC = {5, 6};
mapping1.put(0, childrenA);
mapping1.put(1, childrenB);
mapping1.put(2, childrenC);

// This tree is:
//        / \
//       1   2
//      /\   /\
//     3  4 5  6

HashMap<Integer, int[]> mapping2 = new HashMap<Integer, int[]>();
int[] childrenD = {1, 4};
int[] childrenE = {3, 8};
int[] childrenF = {9, 2};
int[] childrenG = {6, 7};
mapping2.put(5, childrenD);
mapping2.put(1, childrenE);
mapping2.put(4, childrenF);
mapping2.put(3, childrenG);

// This tree is:
//        /   \
//       1     4
//      /\    / \
//     3  8  9  2
//    /\
//   6  7

// lca(head1, 1, 5) should return 0
// lca(head1, 3, 1) should return 1
// lca(head1, 1, 4) should return 1
// lca(head1, 0, 5) should return 0
// lca(head2, 4, 7) should return 5
// lca(head2, 3, 3) should return 3
// lca(head2, 8, 7) should return 1
// lca(head2, 3, 0) should return null (0 does not exist in the tree)
}

public static TreeNode lca(TreeNode root, int j, int k) {
Stack<TreeNode> pathToJ = pathToX(root, j);
Stack<TreeNode> pathToK = pathToX(root, k);
if (pathToJ == null || pathToK == null) {
return null;
}

TreeNode lcaToReturn = null;

while (!pathToJ.isEmpty() && !pathToK.isEmpty()) {
TreeNode jPop = pathToJ.pop();
TreeNode kPop = pathToK.pop();
if (jPop == kPop) {
lcaToReturn = jPop;
} else {
break;
}
}
return lcaToReturn;
}

public static Stack<TreeNode> pathToX(TreeNode root, int x) {
if (root == null) {
return null;
}

if (root.value == x) {
Stack<TreeNode> path = new Stack<TreeNode>();
path.push(root);
return path;
}

Stack<TreeNode> leftPath = pathToX(root.left, x);
if (leftPath != null) {
leftPath.push(root);
return leftPath;
}

Stack<TreeNode> rightPath = pathToX(root.right, x);
if (rightPath != null) {
rightPath.push(root);
return rightPath;
}

return null;
}

// A function for creating a tree.
// Input:
// - mapping: a node-to-node mapping that shows how the tree should be constructed
// - headValue: the value that will be used for the head ndoe
// Output:
// - The head node of the resulting tree
public static TreeNode createTree(HashMap<Integer, int[]> mapping, int headValue) {
HashMap<Integer, TreeNode> nodes = new HashMap<Integer, TreeNode>();
for(Integer key : mapping.keySet()) {
int[] value = mapping.get(key);
TreeNode leftChild = new TreeNode(value[0], null, null);
TreeNode rightChild = new TreeNode(value[1], null, null);
nodes.put(value[0], leftChild);
nodes.put(value[1], rightChild);
}
for(Integer key : mapping.keySet()) {
int[] value = mapping.get(key);
nodes.get(key).left = nodes.get(value[0]);
nodes.get(key).right = nodes.get(value[1]);
}
}
}
```

In this Implementation we have used the Stack and hashmap , Also if you see the Comments all the functionality should be clear .

If you have any issue or you are not able to undertand the program, leave us a comment.