CareerCup

Let h1, h2 be the levels of the two nodes n1, n2 respectively in the tree(find the level by following the parent pointer)
if (h1 > h2) then follow the parent pointer of node n1 move up (h1 - h2) nodes.
else follow the parent pointer of n2 and move up (h2 - h1) nodes.
Now compare both the nodes n1 and n2 and follow the parent pointers until the common ancestor is found.

This is exactly similar problem to "Find the point of intersection of two linked lists". Here the linked lists have the two nodes as heads and the next pointers are the parent pointers all the way to the root.

1. find length of path from node 1 to root via parent ptrs.
2. find length of path from node 2 to root via parent ptrs.
3. In the bigger path traverse difference (mod(len1 - len2)) number of nodes.
4. Traverse one node at a time in both lists till you get common point.

I was asked this same Q..I gave the hash table answer.. then he asked to to optimize it.. he expected

Find out the height of the two nodes in the binary tree. It would take O(n) time. Then, then make one of the pointers to come to the same level as that of the other in the tree. From this point onwards, start traversing the ancestor chain for both the subtrees simultaneously, comparing the parent pointer at each step. The moment the parent pointers come out to be the same, return that parent pointer as the LCA. There are a few edge cases that I am not elaborating here (root being the LCA, straight chain etc), but those can be handled easily.

Analysis: Constant extra space. O(n) worst case runtime.

- Traverse to root and store path. O(log n)
- Find first common point in path (which is the LCA). Can do it in O(n) using hash table.

1) Keep the pointer at one of the child's node. Call it current pointer
2) While current-> data lies between child1->data and child2->data, current = current->parent
3) The moment condition #2 fails, you have stepped out of LCA (i.e you moved to LCA's parent). Keep another pointer to remember previous move and return that.

You can always ask for to confirm. They mean BST when they say *tree*. LCA is specific to the BST.

BTNode* FindingCommonAncestor::findCommonAncestor(BTNode* root, BTNode* a, BTNode* b) {
    queue<BTNode*> *q1 = new queue<BTNode*>;
    queue<BTNode*> *q2 = new queue<BTNode*>;

    isDescendent(root, a, q1);
    isDescendent(root, b, q2);

    int sizeA = q1->size();
    int sizeB = q2->size();

    hash_set<BTNode*> set;
    for ( int i = 0; i < sizeA; i++ ) {
        set.insert((BTNode*) q1->front());
        q1->pop();
    }
    
    for  ( int i = 0; i < sizeB; i++ ) {
        BTNode* node = q2->front();
        if ( set.count(node) ) {
            delete q1;
            delete q2;
            return node;
        }
        q2->pop();
    }

    delete q1;
    delete q2;
    return NULL;
}

bool FindingCommonAncestor::isDescendent(BTNode* root, BTNode* node, queue<BTNode*> *q) {
	if ( root == node ) {
		q->push(node);
		return true;
	} else if ( root->left && isDescendent(root->left, node, q) ) {
        q->push(root);
        return true;
    } else if ( root->right && isDescendent(root->right, node, q) ) {
        q->push(root);
        return true;
    }

    return false;
}

You cant traverse tree. only children are pointing to their parents. There is no pointer from parent to child

Yeo1 ..Can you please explain your logic?

He is basically adding all the parent nodes of, say, first node to a hash table. Next he searches the hash table for parent nodes of the second node. The first match is the common ancestor. I am wondering if there is a more efficient solution. This solution has complexity of O(lg(n)).

http://www.careercup.com/question?id=254667&form=comments

First we need to have a list of leaf nodes in a queue. Extract node from queue and we move up to its parent and at each stage we compare the parent element with two given node values.If both are greater and if the node is not already visited then we move up to the parent and we mark the parent node as visited. If the parent node value is in between the two given node values then we found our ancestor.If the node is already visited or we reached the root node or both the node values are lesser than the current node when traversing from child to parent then we start the same traversal from the next leaf node.

from the two given node, traverse up to the root, when doing so:

1. reverse the child-parent pointer alone the path
2. record the depth of each node
3. then it problem becomes same as the other problem from amazon

this problem is variant of "linked list converge point problem".

the two child nodes are head of the linked list and root is tail. we have to find out the 1st node at which they converge.

So, use the standard method, find length and ...

I don't think Thiyanesh solution will work......especially when both are at same level.....Just assume when one is at level n on left side of root and other is on level n on right side.............

I think good way to solve it is to traverse one side and put all the pointer in link list in order that we got it and then traverse another list and start comparing it and stop when you found a match. Maximum is that we have to (2logn) moves if lowest common ancestor is a root itself........

Since we have not given the keys also, so I don't think we can do it less than logn......Also, in any case worst case can be less than logn............

I think good way to solve it is to traverse one side till root from one node and put all the pointer in link list in order that we got it and then traverse another list and start comparing it and stop when you found a match. Maximum is that we have to (2logn) moves if lowest common ancestor is a root itself........

If we are not given the keys or tree is not BST, then I don't think we can do it less than logn......Also, in any case worst case it cannot be less than logn............

If we know the key then we can traverse the elements going towards the parents.

Suppose that n1 and n2 are two nodes and key1 and key2 are values at these nodes respectively.
Step1: Get the largest of two. Now largest value be on right side of common ancestor and smaller value be on left side of common ancestor and both will be on either right side or left side of parent of common ancestor. So, we can use this property to find the common ancestor.

Step2: Start from smaller key and start moving towards root. If value at parent is less than value at current node then it cannot be common ancestor as smaller value lies on left side of common ancestor. So check next node. And if it is greater than node1, then node1 lies on left side of this ancestor of node1 so this ancestor can be a lowest common ancestor. Go to step 3 to check condition on parent of common ancestor.

Step3: For parent of common ancestor, Check that now both node1 and node2 either should lie on left side or on right side. If even one condition is true then you hit the parent node in step2, otherwise go up one step and repeat from step2. Code for it is as follows:

findCommonAncestor( node1, node2)// Assume node 1 is smaller than node2
{
parent = node1->parent;
while(parent)
{
if(parent->key < node1->key)
continue;
else
{
parentParent = parent->parent;

if((parentParent->key < node1->key && parentParent->key < node2->key) || (parentParent->key > node1->key && parentParent->key > node2->key))
return parent;
else
parent=parentParent;
}
}
}

@Kunal
If one of the node is on the left side of the root and other is on the right side of the root, then root will be the LCA as per my above post.

But if the question really meant, "we can't compare two nodes(address)", then i don't have an answer now.("The nodes do not have any key elements or any other data to identify itself." as per the question)

Please do correct if i am missing something.

I would prefer to traverse one path fully till root, everytime putting the value in a hash table. now,start traversing for 2nd node and stop as soon as you get the node's value in the hash table.

2 ways:
1) Traverse to the root, following the parent chain of one node, and preserving each ancestor in a hashtable. In the second pass, traverse up the ancestor chain of the second node, looking for each ancestor of it in the ancestor map of the first node. The first ancestor in the ancestor chain of the second node that appears in the ancestor map of the first node, is the LCA. (same solution as given in the last post)

Not a very efficient process given the need for extra space to store the ancestor chain.

Analysis: O(n) worst case space and time complexity.

2) Find out the height of the two nodes in the binary tree. It would take O(n) time. Then, then make one of the pointers to come to the same level as that of the other in the tree. From this point onwards, start traversing the ancestor chain for both the subtrees simultaneously, comparing the parent pointer at each step. The moment the parent pointers come out to be the same, return that parent pointer as the LCA. There are a few edge cases that I am not elaborating here (root being the LCA, straight chain etc), but those can be handled easily.

Analysis: Constant extra space. O(n) worst case runtime.

int getLevel(node *ptr)
{
	int level = 0;
	while (ptr)
	{
		level++;
		ptr = ptr->parent;
	}
	return level;
}

node *getCommonAncestor(node *ptr1, node *ptr2)
{
	int h1, h2, diff;
	h1 = getLevel(ptr1);
	h2 = getLevel(ptr2);
	if (h1>h2)
	{
		diff = h1-h2;
		while (diff-- && ptr1)
			ptr1 = ptr1->parent;
	}
	else if (h2>h1)
	{
		diff = h2-h1;
		while (diff-- && ptr2)
			ptr2 = ptr2->parent;
	}
	while (ptr1 && ptr2)
	{
		if (ptr1->parent == ptr2->parent)
			return ptr1->parent;
		ptr1 = ptr1->parent;
		ptr2 = ptr2->parent;
	}
	return NULL;
}

find solution in my name

can be slightly modified the node of tree if yes then i will add a flag to each node
from first pointer move towards it's parent till root
while moving
set the flag value
now start moving from second pointer to it's parent while moving chek the flag value
if it's already set then return that value otherwise keep on moving towards root until u get a node with flag value has been set.

typedef struct node_t
{
	node_t* parent;
	node_t* left;
	node_t* right;
} NODE, *PNODE;


PNODE FirstCommonAncestor(PNODE n1, PNODE n2)
{
	int n1Level = GetLevel(n1);
	int n2Level = GetLevel(n2);
	
	while(n1Level < n2Level)
	{
		n1 = n1->parent;
		--n1Level;
	}
	
	while(n2Level < n1Level)
	{
		n2 = n2->parent;
		--n2Level;
	}
	
	while(n1 != n2)
	{
		n1 = n1->parent;
		n2 = n2->parent;
	}
	
	return n1;
}

int GetLevel(PNODE n)
{
	int level = 0;
	while(n->parent)
	{
		n = n->parent;
		++level;
	}
	return level;
}

i THInk it easy because u have given the parent pointer to each node
wo we can traverse up by chking pointer node
so if at ny time we got same parent it is the answer

CODE:


node* sol(node*ch1,node*ch2)
{
node*k1=ch1;
vector<node*>v1;
while(k1!=NULL)
{
v1.push_back(k1);
k1=k1->parent;
}
vector<node*>v2;
while(k2!=NULL)
{
v2.push_back(k2);
k2=k2->parent;
}
// now traverse form last in both veotrs the last node which is eqal is both is the answer
reverse(v1.begin(),v1.end());
reverse(v2.begin(),v2.end());
for(int i=-1;i<min(v1.size(),v2.size());i++)
{
if(v1[i+1] !=v2[i+1] )return v1[i];
}
}

No specification about extra space so I propose using a stack.

Node* LowestCommonAncestor(Node* node1, Node* node2)
{
  if(!node1 && !node2)
    return null;
    
  if(!node1 || !node2)
    // Ask interviewer what needs to be returned here.
    
  Stack<Node*> s1 = new Stack<Node*>();
  Stack<Node*> s2 = new Stack<Node*>();
  
  Node* temp = node1;
  while(temp)
  {
    s1.push(temp);
    temp = temp->parent;
  }
  
  temp = node2;
  while(temp)
  {
    s2.push(temp);
    temp = temp->parent;
  }
  
  // Nodes from different trees
  if(s1.peek != s2.peek)
    return null;
  
  while(s1.peek == s2.peek)
  {
    temp = s1.pop;
    s2.pop;
  }
  
  return temp;
}

famous LCA problem,

with O(NlogN) preprocessing, you can do O(log h) for each LCA query, where h is the max level of tree.

well, but I'm sure the interview is expecting something easier~

current=root.
while(current!=NULL){
Do a BFS (or any tree traversal) on left node.(current->left) 
  - if both children are in left node, then now current=root->left. 
  - if left node has only one child, return root as ansector
  - else, current=root->right
}