Given a binary tree, and 3 nodes x,y,z write a function which returns true if y lies in the path between x and z and false otherwise

int find_y_in_xz_path(Tree t, Node *y, Node *z, int yfound)
{
if(!t)
return 0;

if(t == z)
{
return yfound;
}
else if(t == y)
{
yfound = 1;
}

if(find_y_in_xz_path(t->left, y, z, yfound))
return 1;

return find_y_in_xz_path(t->right, y, z, yfound);

}

int main()
{
find_y_in_xz_path(x,y,z,0);
}
Advertisements

3 thoughts on “Given a binary tree, and 3 nodes x,y,z write a function which returns true if y lies in the path between x and z and false otherwise

  1. Hey your solution looks cool:-)Can you modify your code to check paths going upwards too.. I mean.. for a tree like this 4 / \ 5 6it should return true for 4 lying between 5 and 6I have seen this often asked in interviews

  2. I guess while making the second call to find, you should reset yfound to zero(0). Because if the node y is on the left sub-tree and node z on the right sub-tree, then after first exploring the left sub-tree the value of yfound will be set to 1 and will always remain one.Let me know if i'm wrong.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s