Amazon Interview Question
Software Engineer / DevelopersCountry: India
Using a BFS you can find it. You don't care about the path but length of the path when performing the search.
function find_ancesstor (tree, a, b) {
var shortest_distance = Infinity;
var result = null;
traverse(tree, []);
return result.data;
function traverse (node) {
if(!node) return;
var distance = find_distance(node, a, b);
if(distance && distance < shortest_distance){
shortest_distance = distance;
result = node;
}
traverse(node.left);
traverse(node.right);
}
}
function find_distance (node, a, b) {
var distance_a = null,
distance_b = null;
traverse(node, 0)
function traverse (node, distance) {
if(!node) return;
if(node.data == a){
distance_a = distance;
}
if(node.data == b){
distance_b = distance;
}
distance += 1;
traverse(node.left, distance);
traverse(node.right, distance);
}
if(distance_a && distance_b){
return distance_a + distance_b;
}
return null;
}
// 8
// 4 12
// 2 6 10 14
// 1 3 5 7 9 11 13 15
var tree = {"data":8,"left":{"data":4,"left":{"data":2,"left":
{"data":1,"left":null,"right":null},"right":{"data":3,
"left":null,"right":null}},"right":{"data":6,"left":
{"data":5,"left":null,"right":null},"right":{"data":7,
"left":null,"right":null}} },"right":{"data":12,"left":
{"data":10,"left":{"data":9,"left":null,"right":null},
"right":{"data":11,"left":null,"right":null}},"right":
{"data":14,"left":{"data":13,"left":null,"right":null},
"right":{"data":15,"left":null,"right":null}} }};
console.log(find_ancesstor(tree, 9, 11));
Its a sample code for k=3 where n1, n2 and n3 are 3 nodes. Can be generalized further by taking n1, n2, n3 in array. Basic idea is when we find a node, parent is updated that node is found. So parent can see if total k nodes are found till now or not.
int LCA_(bt_ *root, int k, int n1, int n2, int n3)
{
if(root==NULL)
return 0;
int total = 0;
int found_l = LCA_(root->left,k,n1,n2,n3);
int found_r = LCA_(root->right,k,n1,n2,n3);
total = found_l+found_r;
if(root->data == n1 ||
root->data == n2 ||
root->data == n3)
{
total++;
}
if(total == k)
{
printf("LCA %d ",root->data);
total = 0;
}
return total;
}
Find the path for each node, and compare the path.
BinaryTreeNode getLatestCommonParent(BinaryTreeNode root, ArrayList<BinaryTreeNode> nodes){
if(root == null){
return null;
}
boolean[] boolResult= new boolean[nodes.size()];
ArrayList<ArrayList<BinaryTreeNode>> pathList = new ArrayList<ArrayList<BinaryTreeNode>>();
for(int i = 0; i < nodes.size(); i++){
if(nodes.get(i) == null){
return null;
}
boolResult[i] = getNodePath(root, nodes.get(i), pathList.get(i));
}
for(int i = 0; i < nodes.size(); i++){
if(!boolResult[i]){
return null;
}
}
boolean mark = false;
int loc = 0;
BinaryTreeNode LCA = root;
while(!mark){
for(int i = 0; i < nodes.size(); i++){
if(pathList.get(i).get(loc) == null || pathList.get(i).get(loc) != pathList.get(0).get(loc)){
mark = true;
}
}
}
return LCA;
}
private boolean getNodePath(BinaryTreeNode root,
BinaryTreeNode node, ArrayList<BinaryTreeNode> path) {
if(root == null){
return false;
}
if(root == node){
path.add(node);
return true;
}
path.add(node);
if(getNodePath(root.left, node, path)){
return true;
}
if(getNodePath(root.right, node, path)){
return false;
}
return false;
}
/* Function to find LCA of n1 and n2. The function assumes that both
n1 and n2 are present in BST */
struct node *lca(struct node* root, int n1, int n2)
{
if (root == NULL) return NULL;
// If both n1 and n2 are smaller than root, then LCA lies in left
if (root->data > n1 && root->data > n2)
return lca(root->left, n1, n2);
// If both n1 and n2 are greater than root, then LCA lies in right
if (root->data < n1 && root->data < n2)
return lca(root->right, n1, n2);
return root;
}
public static TreeNode LCA(TreeNode root, TreeNode[] nodes) {
if (root == null) {
return null;
}
for(int i=0;i<nodes.length;i++) {
if (root == nodes[i]) {
findCount++;
return root;
}
}
TreeNode leftRoot = LCA(root.left, nodes);
TreeNode rightRoot = LCA(root.right, nodes);
if (leftRoot != null && rightRoot != null) {
// if child1 and child2 are on both sides
return root;
}
// either one of child1 or child2 is on one side
// OR child1 or child2 is not in L&R subtrees
return (leftRoot != null) ? leftRoot : rightRoot;
}
I think, we can boil down this question to a simpler one.
Basic concept is that we need to find two extreme nodes (one furthest left, one furthest right) in between all the 'k' given nodes. So, any nodes which lie in between these nodes will be under those two's LCA i.e. divergent point of the paths connecting root and these two nodes will be the LCA of all 'k' nodes.
So, the algo is:
- Psycho January 08, 2016