Binary tree recursive problem

1
votes

I found this problem and I am not very sure if my approach approach is right:

"A binary tree can be encoded using two functions l and r such that for a node n, l(n) gives the left child of n(or nil if there is none) and r(n) gives the right child(or nil if there is none).Let Test(l,r,x) be a simple recursive algorithm for taking a binary tree encoded by the l and r functions together with the root node x for the binary tree, and returns "yes" if no node in the tree has exactly one child. Give the pseudocode for this algorithm."

I tried this:

test(l,r,x)
  if((l(x)!=null && r(x)!=null) || (l(x)==null && r(x)==null)) 
     return "yes"
   else return "no"

  if(test(l,r,l(x))=="yes") test (l,r,l(x)) else return "no"
  if(test(l,r,r(x))=="yes") test (l,r,r(x)) else return "no"

 return "yes"

Is it correct? If l and r are functions, why are they passed as normal parameters when the function is called?

Thank you in advance for your answers!

3
algorithmrecursionbinary-treepseudocode
What makes you think that functions cannot be treated as "normal parameters"? What's wrong with that? You seem to imply something like that in your question. - AnT
@AndreyT depending on OP's background, he may not be aware that some languages allow that feature. - corsiKa
In any event, he seemed to actually pick up on the concept that they're passed like normal parameters quite well, in my estimation. - corsiKa

3 Answers

3
votes

You have three basic conditions: both children are null, one child is null, or neither child is null. I'd test them in that order as well (because it simplifies the logic a bit):

if l(x) == null && r(x) == null
    return true;
if l(x) == null || r(x) == null  // only need inclusive OR, due to previous test.
    return false;
return test(l, r, l(x)) && test(l, r, r(x))

As far as passing l and r as parameters goes, it all depends: some languages (e.g., functional languages) allow you to pass a function as a parameter. Others (e.g., C, C++, etc.) have you pass a pointer to a function instead -- but it's pretty much irrelevant. A few won't let you pass anything like a function, in which case you'd have to hardwire it in. In this case, you're not really gaining much (anything?) by passing l and r as parameters anyway. Passing a function as a parameter is useful primarily when/if the receiving function doesn't know what function it's going to receive a priori (which it does here).

1
votes

I don't think this is correct. The problem I see is in the first step:

if((l(x)!=null && r(x)!=null) || (l(x)==null && r(x)==null)) 
    return "yes"
else return "no"

The problem is that you cannot determine the 'yes' for the entire tree at the first step. What you have to do is break it up into components:

if this node has both children
    return the result of test(l,r,l(x)) && (test(l,r,r(x))
if this node has no children
    return true
if this node has 1 child
    return false

as per your last question ("If l and r are functions, why are they passed as normal parameters when the function is called?"), the answer is that they don't have to be passed as parameters. That's just the notation they chose when they said "A binary tree can be encoded using two functions l and r [...]"

1
votes

the first thing you do is either return yes or no, so the last part is unreachable.

I would change it so that if you have one child, you return no, otherwise you return yes or no depending on if your children meet the criteria.

test(l,r,x)
  if((l(x)!=null && r(x)==null) || (l(x)==null && r(x)!=null)) 
     return "no"
  if(l(x) == null && r(x) == null) 
    return "yes"
  return test(l,r,l(x)) && test(l,r,r(x))