Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
struct node{
int data;
struct node* left;
struct node* right;
};
struct node* leastCommonAncestor(struct node* root,struct node* p,struct node* q){
if(root==NULL){
return NULL; //If no root leastCommonAncestor is NULL.
}
if(root==p || root==q){
return root; // Check if the current root is equal to any of the desired node.
}else{
struct node* l=leastCommonAncestor(root->left, p, q); // Find LCA in left of the tree
struct node* r=leastCommonAncestor(root->right, p, q); // Find LCA in right of the tree
if(l!=NULL && r!=NULL){
return root;
}else if(l!=NULL && r==NULL){
return l;
}else if(l==NULL && r!=NULL){
return r;
}else{
return NULL;
}
}
}
private static void leastCommonAncestor(final TreeNode root, TreeNode n1, TreeNode n2) {
Stack<TreeNode> leftPath = getPath(root, n1);
Stack<TreeNode> rightPath = getPath(root, n2);
while (!leftPath.isEmpty() && !rightPath.isEmpty()) {
int lca = 0;
if ((lca = leftPath.pop().value) == rightPath.pop().value) {
System.out.println(lca);
}
}
}
private static Stack<TreeNode> getPath(TreeNode root, TreeNode n) {
HashMap<TreeNode, Object> visitedMap = new HashMap<>();
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
visitedMap.put(root, null);
while (!stack.isEmpty()) {
TreeNode t = stack.peek();
if (t.value == n.value) {
return stack;
} else if (t.left != null && !visitedMap.containsKey(t.left)) {
visitedMap.put(t.left, null);
stack.push(t.left);
} else if (t.right != null && !visitedMap.containsKey(t.right)) {
visitedMap.put(t.right, null);
stack.push(t.right);
} else {
stack.pop();
}
}
return stack;
}
struct TreeNode {
TreeNode(int in_value = 0) : parent(0), left(0), right(0), value(in_value)
{
}
TreeNode *parent;
TreeNode *left;
TreeNode *right;
int value;
};
int GetNodeLevel(TreeNode *node)
{
int level = 0;
if ( node ) {
TreeNode *parentNode = node->parent;
while(parentNode) {
++level;
parentNode = parentNode->parent;
}
}
return level;
}
TreeNode* GetLeastCommonAncestor(TreeNode *node1, TreeNode *node2)
{
if ( node1 && node2 ) {
int n1level = GetNodeLevel(node1);
int n2level = GetNodeLevel(node2);
while( n1level!=n2level ) {
if ( n1level>n2level) {
--n1level;
node1 = node1->parent;
}
else {
--n2level;
node2 = node2->parent;
}
}
while ( node1 && node2 && node1!=node2 ) {
node1 = node1->parent;
node2 = node2->parent;
}
}
return (node1 && node1==node2) ? node1 : 0;
}
public int LCA(int value1,int value2){
Node node1 = find(value1);
Node node2 = find(value2);
int depth1 = depth(value1);
int depth2 = depth(value2);
if(depth1>depth2)
{
while(depth1>depth2)
{
node1 = node1.getParent();
depth1--;
}
}else if(depth2>depth1)
{
while(depth2>depth1)
{
node2 = node2.getParent();
depth2--;
}
}
while(node1 != null|| node2!= null){
if( node1 == node2)
break;
node1 = node1.getParent();
node2 = node2.getParent();
}
return node1.getValue();
}
A single node can have multiple children.
The idea is to find two paths from the root to the two nodes separately and then find the least common nodes from the two lists.
One possible downside is that we go through the nodes twice for each query node we consider.
However, the space and time [O(number of nodes) both for time and space] complexity remains the same.
Feel free to point out any flaws. :-)
import java.util.ArrayList;
import java.util.List;
import java.util.Iterator;
class Node {
Node children[];
int value;
}
// The recursive method
private boolean findTrail(Node curr, Node node, List trail){
if(curr == node ){
trail.add(curr);
return true;
}
boolean found = false;
for(Node child : curr.children){
found = findTrail(child, node, trail);
if(found){
trail.add(curr);
return true;
}
}
return false;
}
//.................
// Method using the recursive method.
public Node findLeastComAns(Node root, Node A, Node B){
if(root == null || A == null || B == null){
return null;
}
List list1 = new ArrayList();
List list2 = new ArrayList();
boolean found = findTrail(root, A, list1);
if(!found){
return null;
}
found = findTrail(root, B, list2);
if(!found){
return null;
}
Iterator<Node> itr1 = list1.listIterator();
Iterator<Node> itr2 = list2.listIterator();
Node common;
Node least = null;
while(itr1.hasNext()&&itr2.hasNext()){
common = itr1.next();
if(common == itr2.next()){
if(least == null){
least = common;
}
else if(least.value > common.value){
least = common;
}
}
}
return least;
}
algo:
1# find path to both of the nodes from root lets say pPath and qPath.
2# compare paths till the both start getting on different way. the previous node where the are departing will be least common ancestor.
Note: space complexity will be high but as i know time complexity will be maximum O(n+n+n) i.e. O(n)
comments and improvements are welcome.
dff
- explorer.bit January 21, 2013