The Gateway to Computer Science Excellence
0 votes
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 by Veteran (119k points)
edited by | 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

1 Answer

0 votes
Option 1 should be right
by Loyal (5.7k points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,324 answers
198,405 comments
105,169 users