## Microsoft Amazon Interview Question Software Engineer / Developers

- 0of 0 votes
Given a tree where each node points to its parent, find LCA of two nodes. Write test cases for same.

The main idea of the solution is — While traversing Binary Search Tree from top to bottom, the first node n we encounter with value between n1 and n2, i.e., n1 < n < n2 is the Lowest or Least Common Ancestor(LCA) of n1 and n2 (where n1 < n2). So just traverse the BST in pre-order, if you find a node with value in between n1 and n2 then n is the LCA, if it's value is greater than both n1 and n2 then our LCA lies on left side of the node, if it's value is smaller than both n1 and n2 then LCA lies on right side.

Implementation:

view source

print?

#include <stdio.h>

#include <stdlib.h>

/* A binary tree node has data, pointer to left child

and a pointer to right child */

struct node

{

int data;

struct node* left;

struct node* right;

};

struct node* newNode(int );

/* Function to find least comman ancestor of n1 and n2 */

int leastCommanAncestor(struct node* root, int n1, int n2)

{

/* If we have reached a leaf node then LCA doesn't exist

If root->data is equal to any of the inputs then input is

not valid. For example 20, 22 in the given figure */

if(root == NULL || root->data == n1 || root->data == n2)

return -1;

/* If any of the input nodes is child of the current node

we have reached the LCA. For example, in the above figure

if we want to calculate LCA of 12 and 14, recursion should

terminate when we reach 8*/

if((root->right != NULL) &&

(root->right->data == n1 || root->right->data == n2))

return root->data;

if((root->left != NULL) &&

(root->left->data == n1 || root->left->data == n2))

return root->data;

if(root->data > n1 && root->data < n2)

return root->data;

if(root->data > n1 && root->data > n2)

return leastCommanAncestor(root->left, n1, n2);

if(root->data < n1 && root->data < n2)

return leastCommanAncestor(root->right, n1, n2);

}

/* Helper function that allocates a new node with the

given data and NULL left and right pointers. */

struct node* newNode(int data)

{

struct node* node = (struct node*)

malloc(sizeof(struct node));

node->data = data;

node->left = NULL;

node->right = NULL;

return(node);

}

/* Driver program to test mirror() */

int main()

{

struct node *root = newNode(2);

root->left = newNode(1);

root->right = newNode(4);

root->right->left = newNode(3);

root->right->right = newNode(5);

/* Constructed binary search tree is

2

/ \

1 4

/ \

3 5

*/

printf("\n The Least Common Ancestor is \n");

printf("%d", leastCommanAncestor(root, 3, 5));

getchar();

return 0;

}

Here is a generic solution for finding LCA for two values in a general binary tree. Now for BST, we can do some simple trimming of the recursion so it will be fast. Leave to you to think:

```
// find least common ancestor in a binary treeu.
int max_level = -1;
int lca_value = 0;
// node: current node.
// a, b: two values we're looking their LCA for. they don't need to
// to be ordered, that a not necessarily smaller than b.
// pa, pb: returns to call that whether value a and/or value b exists
// in this sub tree with node as its root.
// level: how deep are we in the tree.
// assumption the all the values in the tree are unique.
void FindLca(NODE *node, int a, int b, bool *pa, bool *pb, int level)
{
*pa = *pb = false;
if (!node) goto exit;
if (node->value == a) { *pa = true; }
if (node->value == b) { *pb = true; }
bool la = false, ra = false, lb = false, rb = false;
if (node->left)
{
FindLca(node->left, a, b, &la, &lb, level + 1);
}
if (node->right)
{
FindLca(node->right, a, b, &ra, &rb, level + 1);
}
if (!*pa) { *pa = la || ra; }
if (!*pb) { *pb = lb || rb; }
exit:
if (*pa && *pb && level > max_level)
{
max_level = level;
lca_value = node->value;
}
}
```

Here is a simpler solution. As you find parent keep on inserting in a hash table. Look for other nodes parent in hash table. First point where its found is LCA.

```
Node* LCA(Node* root, Node* x, Node* y) {
if(x == root || y == root || x == NULL || y == NULL) { return NULL; }
hash_set<Node*> parents;
while(x->parent) {
parents.insert(x->parent);
x = x->parent;
}
while(y->parent) {
if(parents.find(y->parent) != parents.end()) { return y->parent; }
y = y->parent;
}
return NULL;
}
```

Find the depth of both nodes. Lets say depth of node X be 15 & node Y be 10. Then traverse node X (larger depth) towards parent by 5 (15-10) nodes. Lets say it comes out to be Z.

After this traverse both Z & Y towards parent node & keep on matching them. First common match is a LCA.

Mike...

your answer seems to be right.

To just make it clear-the node with greater depth should be designated as X.

It works!

Thankyou

This will work but you'll be making many more traversals through the tree since you need to now first find the depth of each node which is O(n) operation for each node.

It's a trade-off between space and time though - with your approach, at most constant extra space is required but 4 O(n) passes. With the hashtable approach above, you can do it with just 2 O(n) passes through the tree but you will need O(n) space.

Its easier than mentioned in the answers above. Find the shorted depth, let's call it s. Traverse the node with higher depth up s times to its parent and you are done !

What if traversing the larger depth node up 5 times(if 5 is the diff between the depth of two nodes) takes you past the LCA of the two nodes .... ??? IN this case the aboce solution wont work...

Let us have two stacks S1 and S2. Let a and b be the two nodes for which LCA have to be found. Move up from 'a' and store the way(nodes) in S1. Move up from 'b' and store the way in S2.Now pop the stacks until a mismatch occurs or one of the path ends. The node before the first mismatch or the the last node before one of the stacks become empty is the LCA.

This code should do the trick :

1 traversal until encounter the first node;

2 check if second node is under the first node, if so, the first node self is LCA, otherwise ,go3

3. go back with parent pointer until found one which have right subtree and the second node is in it , then this node is LCA.

```
Node * LCA(Node *root, Node *n1, Node *n2)
{
bool find = false; // keep track of if lca is found or not
Node *lca = NULL;
DoLCA(root, n1, n2, find, lca);
Return lca;
}
Void DoLCA(Node *root, Node *n1, Node *n2, bool &find, Node *&lca)
{
if ( root == NULL)
Return ;
// encounter the first node
If ( root == n1 || root == n2)
{
Node *Second = root == n1 ? n2 : n1;
If (Cover(root, second))
Lca = root;
Else
{
While(root)
{
root = root->parenet;
If(root->Right && Cover(root->Right, second))
{
Lca = root;
Break;
}
}
}
Find = true;
Return;
}
// go left
DoLCA(root->Left, n1, n2, second, flag, lca);
If (find)
Return; // lca found , just return, no need to go right
// go right
DoLCA(root->Left, n1, n2, second, flag, lca);
}
```

This code should do the trick :

1 traversal until encounter the first node;

2 check if second node is under the first node, if so, the first node self is LCA, otherwise ,go3

3. go back with parent pointer until found one which have right subtree and the second node is in it , then this node is LCA.

```
Node * LCA(Node *root, Node *n1, Node *n2)
{
bool find = false; // keep track of if lca is found or not
Node *lca = NULL;
DoLCA(root, n1, n2, find, lca);
Return lca;
}
Void DoLCA(Node *root, Node *n1, Node *n2, bool &find, Node *&lca)
{
if ( root == NULL)
Return ;
// encounter the first node
If ( root == n1 || root == n2)
{
Node *Second = root == n1 ? n2 : n1;
If (Cover(root, second))
Lca = root;
Else
{
While(root)
{
root = root->parenet;
If(root->Right && Cover(root->Right, second))
{
Lca = root;
Break;
}
}
}
Find = true;
Return;
}
// go left
DoLCA(root->Left, n1, n2, second, flag, lca);
If (find)
Return; // lca found , just return, no need to go right
// go right
DoLCA(root->Left, n1, n2, second, flag, lca);
}
```

LCA is a binary search tree (BST) is simple. For any nodes x and y, the LCA is the first node which lies between x and y starting from root.

Node getLCA_BST(Node root, Node x, Node y):

Node curr = root

while !(x < curr && curr < y): // x.value < curr.value

if curr < x && curr < y:

curr = curr.right

else: //x < curr && y < curr

curr = curr.left

return curr // assume x and y are in the tree

This problem reduces to finding the point of intersection of two linked lists (because parent pointers are given).

- AV on October 31, 2010 Edit | Flag Reply