118 views

Consider the following function with a binary tree with atleast one node:

int path(struct node *x, int len){
if(x==NULL) return B;
else return A;
}

Assume the above function is used “to check the given binary tree has any path with specified length from root to the leaf node”. Let $T$ be a binary tree with root pointed by $x.$  The function path $(x,10)$ returns non-zero if there exists any path from root to leaf has a path length $10.$ Otherwise returns $0$. Find $B$ and $A$ with recursive call of path?

$(1)$ $A$ is $path(x->left,len-1)||path(x->right,len-1)$ ,$B$ is $(len==1)$

$(2)$ $A$ is $path(x->left,len-1)||path(x->right,len-1)$ ,$B$ is $(len== -1)$

which of these two option correct? Please Explain.

in DS
edited | 118 views
0
0
x->leaf or x->left??
0
yes, that is correct. But will that naming much difference in code?
0
I am unable to solve this.. :(
0
Where r u getting problem?
0
My sems are going on..will try again later.. :)
0
oh,ok. no prob :)
0
Sorry for the wong explanation.
1.At every step of the func call len is reduced by 1,so when x has no left/right child i.e when x=NULL final len will be 1.
so (x==NULL) evaluates true and len==1 also evaluates true and returns non-zero

2.if no path length==len exist,then when x hits NULL ,len would not be 1 ,,,so returns 0

option 1 should be ryt
0

But how do they know, there is a path length 10 from root to leaf

0

@Abhishek Kumar 40

Still how do it check path length $10.$

Can be a path length less than $10$ too?

0
obviously ,they just have given example to make u undrstand
0

@Abhishek Kumar 40

Ans given 2)

0
it can't be trace out by taking eg
0
On less than path length 10 it would still give true if left branch or right branch finishes earlier