Amazon Interview Question Software Engineer / Developers
here is how I would do it:
1. if it is a BST, the find operation can be altered such that it does a search for not just 1 element but 2 elements, and when the decision is coincidental, go ahead in that direction. whenever the first contradiction occurs, return a pointer to the current node.
2. if it is not a BST, you can use the property that the node asked for is the only node for which the 2 nodes lie in different subtrees. for all nodes above it, they lie in the same subtree. for all nodes below it, one of the node doesn't exist.
So in other words, you do not have a solution for it in the case that it is not a BST, so you just state the obvious properties of the solution and hope for the best?
@ryan ...
for a non BST ( m-tree ) here is how you can do it ....
if you do a find operations, and find a direct path from the root to each of the nodes, storing the return path from the each of node to root. store the intermediate root pointers in a list. compare the lists in the reverse order, and you have the deepest common ancestor.
To reiterate the common ancestor solution.
TreeNode ClosestAncestor(TreeNode root, TreeNode node1, TreeNode node2)
{
if(NULL == root) return NULL;
if(root->left == node1 || root->right == node1 || root->left == node2 || root->right == node2)
return root;
else
{
TreeNode left,right;
left = ClosestAncestor(root->left,node1,node2);
right = ClosestAncestor(root->right,node1,node2);
return (left && right)?root:(left?left:right);
}
}
Do a depth first search.
When we find the first element, Save the position of the pointer of the parent on the stack. After that continue search for the next element, if at any point the parent pointer saved is to be removed, then change the parent pointer to point to the previous element, and continue the search till u find the sencond elemnt. When the seconds element is found, then ur parent pointer is the deepest common ancestor.
This can be used for any tree.
PS: For this one needs to be aware of the depth first algo, hwere u push the elements on the stack during the process.
why traversal at all. If we have two node (data), say x & y. First sort x & y. smaller one say x, MUST be leftSub tree & bigger one (y) MUST be in right sub-tree of the deepest ancestor.
There's an exception for tree like
4
\
6
\
7
\8
In such cases both are in same subtree.
So algo is:
while(root) {
if (root.data > x && root.data < y) {
break;
}
if (root.data > y ) {
if (root.left.data = y)
break;
root = root.left;
}
else if (root.data < y) {
if (root.right.data == y)
break;
root = root.right;
}
}
The lowest common ancestor (LCA) is a concept in graph theory and computer science. Let T be a rooted tree with n nodes. The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).
Google, "lowest common ancestor" for wikipedia results and exact algorithm.
Node * DeepestAncestor(Node *root, Node *n1, Node *n2) {
if(!root)
return NULL;
if(node1 == root || node2 == root)
return root;
bool flag1 = Check(root->left,node1);
bool flag2 = Check(root->left,node2);
if(flag1 && flag2)
return DeepestAncestor(root->left,node1,node2);
else if(!flag1 && !flag2)
return DeepestAncestor(root->right,node1,node2);
else
return root;
}
bool Check(Node *root, Node *n) {
if(!root)
return false;
else
return Check(root->left,n) || Check(root->right,n);
}
Found the above question on glass door. The solution I could think is -
- abhispra February 17, 20101>Find the paths to the nodes
2>Turns into a problem of finding the common node of two linked list.
3>Use the standard technique of finding the length and then finding the common point.
Can anybody confirm if this approach is fine. Also any other solution with better time complexity?? Appreciate the help.