CareerCup

I doubt they will give you the parent pointers, if parent pointers not given i think its merely asking you to find the LCA (lowest Common Ancestor)

If the address of the head node is not given then this problem is quite tricky.
Other wise we store the address of the nodes in the path from the root to the first node. Then we go from the root to the 2 node. At each node we encounter we check the earlier stored path ....

We can do something like this

while (LastNode in pathp not present in pathq &&
       LastNode in pathq not present in pathp) {
  p = p->parent();
  q = q->parent();
  Append p in the list pathp
  Append q in the list pathq
}

We can do something like this

while (LastNode in pathp not present in pathq &&
       LastNode in pathq not present in pathp) {
  p = p->parent();
  q = q->parent();
  Append p in the list pathp
  Append q in the list pathq
}
Common Ancestor = last node whichever satisfied the criteria to break out of the loop

For a tree as root node is global i think they provide root node also .. if it is the case ..

do this ..

do {
if (node1 == root || node2 == root) {
printf("Invalid i/p");
exit(1);
}
p1=getparent(node1);
p2=getparent(node2);
while (p1 != p2 || p1 != NULL || p2 != NULL) {
p1=getparent(node1);
p2=getparent(node2);
}
if (p1 != NULL || p2 != NULL) {
printf("Invalid i/p");
exit(1);
}
else
print("p1 or p2 which is needed parent");
}


getparent can be a simple recursive function to get each nodes parent. :)

you could do a bfs to get the height and parent of each node(assuming ur given the root ofcourse), then jump to parents of the node which is farther from the root till they're at the same level(you might just encounter the other node as the predecessor now), then race towards the root and check for equality. Space complexity is bad due to the storage for depth and parent, but is faster now.

hey can be Inorder successor or predecessor of particular pointer would be a nearest parent to the pointer with left and right subtree condition

hey can be Inorder successor or predecessor of particular pointer would be a nearest parent to the pointer with left and right subtree condition
Do correct me if i am wrong

bool Find(node *NodeToBeFound, node *StartNode)
{
    if(NodeToBeFound->data == StartNode->data)
        return 1;
    if(Find(NodeToBeFound, StartNode->left) == 1)
        return 1;
    if(Find(NodeToBeFound, StartNode->right) == 1)
        return 1;
}

   node *Parent = FirstNode;
   found = 0;
   while(found == 0)
   {
       Parent = Parent->parent;      
       found = Find(Parent, SecondNode);       
   }
   
   Parent is the required common nearest parent

Node FindNearestParent(Node a,Node b)
{
  List<Node> ParentList = new ArrayList<Node>();
  while(a.parent!=null)
  {
   ParentList.add(a.parent);
   a=a.parent;
  
  }
  while(b.parent!=null)
  {
   if(ParentList.contains(b.parent))
   {
        return b.parent;
      
   }
   b=b.parent;
  
  
  
  }

/* Assuming node structure has a parent pointer */

Node* FindCommonAncestor (node *node1, node *node2) {
        while ( node1 != node2 ) {
                if (node1 != NULL) node1 = node1->parent;

                if (node2 != NULL) node2 = node2->parent;
        }

        return node1;
}

its same as given two link list that merge at a point... find the merging point...
logic:
1) Start pointer1 and count number of nodes to root (len1)
2) Start pointer2 and count number of nodes to root (len2)
3) Max(len1, len2) say len1
4) Move pointer 1 by difference of len1-len2
5) then move both of them together untill you have ptr1!=ptr2

you can also think problem as finding merging node in given two link list and you need to find merging node of this two list which will be actually nearest parent of both head node (given two node of tree). you can think root node as a last node of both list since root->parent=NULL

Assuming, every node of tree has parent field apart from tradition left, right and data field, traverse the tree upwards using parent field.

Let p and q be pointers to any two nodes.

then

while(p->parent != q->parent)
     {
           p = p->parent;
           q = q->parent;
     }   
     NODE *t = p;

Node t is the nearest parent to p and q.