CareerCup

class Node {
public:
Node * left;
Node * right;
Node * parent;
};
leftflag = 0;
rightflag = 0;

Traverse thru right subtree of y and search for z, if found set right flag as 1

Else traverse thru parent/grandparent of y until the parent node is not root
For each parent/grandparent greater than y - Search thru the right subtree of parent
even at root - search thru right subtree of root. If z found set rightflag as 1

If right flag is 0 exit with FALSE

Else Traverse thru left subtree of y and search for x, if found set left flag as 1

Else traverse thru parent/grandparent of y until the parent node is not root
For each parent/grandparent less than y - Search thru the left subtree of parent
even at root - search thru left subtree of root. If x found set leftflag as 1

if leftflag = 0, exit with FALSE status

exit with TRUE status

In most interviews parent node pointer is not allowed. :D
In-order traversal from X,
if we meet Z first,
then return false;
else if we meet Y first,
then In-order traversal from Y.
if we meet Z, then return true;
else return false;
else return false;// meet neither
Of course, it's possible that Z is ancestor of X. Repeat.

Can a run of BFS or DFS do the job

Cant we do this ?
Identify the node that is closer to the root . let it be x.
now search for y in he subtree rooted at x. if not found return false.
Then search for Z in the subtree rooted at y. If found return true else return false

It might work ...

find_ele_inpath(x,y,z) {

if (x == y && x == z) {
return(1); //path exists
}

else if (x == y) {
return find_ele_inpath(x,z,z);
}

else if (x == z) {
return(0);
}

find_ele_inpath(x->left, y, z);
find_ele_inpath(x->right, y, z);

}

boolean findElementPath ( node x , node y, node z, bool bx, bool by, bool bz, node t)
{
   if( !bx && t == x ) bx = true ; 
   else if ( !by && t == y ) by = true ; 
   else if ( !bz && t == z ) bz = true ; 
   else return true ; 
    
   return ( findElementPath (x,y,z,bx,by,bz,t->left) || 
            findElementPath (x,y,z,bx,by,bz,t->right) )

}

There is a fundamental question here -

Do we want to be able to detect patterns of only x - y - z ? or are we also interested in patterns z - y - x as well ? If we are, then the above approaches will not work. YOu will have to add another function that checks for subtrees of z for y, and then subtrees of y for x. This case will not be detected by the initial algorithm.

There is a fundamental question here -

Do we want to be able to detect patterns of only x - y - z ? or are we also interested in patterns z - y - x as well ? If we are, then the above approaches will not work. You will have to add another function that checks for subtrees of z for y, and then subtrees of y for x. This case will not be detected by the initial algorithm.

For example, the above will fail for -

y
   / \
  z   x

How about a variant of Preorder which keeps track of encountered nodes in two bools - left and middle. The trick is to reset the bools - left and middle when we leave a node encountered.

void ModifiedPreOrder(node* root, bool& sucess)
{
   static bool left = false;
   static bool right = false;

   if(node != NULL)
   {
      if(root->data == X)
         left=true;
  
     if((root->data == Y) && (left == true))
         middle = true;

     if(root->data == Z) && (middle == true)
        sucess = true;
     

       PreOrder(node->left, sucess);
       PreOrder(node->right, sucess);

      //Reset status flags when we leave this node.
       if(root->data == X)
       {
         left=false;
         middle=false;
       }

       if(root->data == Y)
          middle= false;
   }
}

Do a euler tour of the tree to find the LCA of the x and z. If common ancestor is y then return true otherwise false.

My main logic here is that any path between two nodes of a tree could only be through their common ancestor.

Correct me if I am wrong
Will this work?
To Check whether y lies between x & z

Find least common ancestor of x and y say A1
Find least common ancestor of z and y say A2

if A1==A2
return true
else
return false

Check my code

int FindXYZ(Tnode *root,Tnode *X,Tnode *Y,Tnode *Z)
{
    if(root==NULL)
        return 0;
    static Tnode *rootnode=NULL;
    static int found=0;
    if(rootnode==NULL)
        rootnode=root;
    int left=FindXYZ(root->left,X,Y,Z);
    int right=FindXYZ(root->right,X,Y,Z);
    if(left==1 && right==1 && found==0)
    {
        if(root==Y)
            found=1;
    }
    if((left==11 || right==11)&&found==0)
    {
        if(root==X || root==Z)
            found=1;
    }
    if(left==10 || right==10)
        found=-1;
    if(left==2 || right==2)
        found=-1;
    if(rootnode==root)
        return found>0;
    if(root==X||root==Z)
        return left+right+1;
    if(root==Y)
        return left+right+10;
    return left+right;
}