1

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!

Improve this question
3
  • 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. Commented Mar 28, 2011 at 17:41
  • 1
    @AndreyT depending on OP's background, he may not be aware that some languages allow that feature. Commented Mar 28, 2011 at 17:43
  • In any event, he seemed to actually pick up on the concept that they're passed like normal parameters quite well, in my estimation. Commented Mar 28, 2011 at 17:53

3 Answers 3

Reset to default
3

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).

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

I personally disagree with the idea of "simplifying" logic to mean it has fewer statements. Whenever your logic is implicit as opposed to explicit, you reduce readability (due to increased programmer thinking required) and increase the chance for bugs.
It's not that it has fewer statements (which it doesn't), but that each statement is itself much simpler to understand. If you insist on doing it the other way, I think it would be best to use an XOR explicitly: if (l(x) == null XOR r(x) == null) rather than the rather convoluted if (l(x) == null && r(x) != null || l(x) != null && r(x) == null). IMO, the latter (all by itself) is harder to read or understand than the entire function as I've written it.
1

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))
Improve this answer

3 Comments

Ok then, but where is the "yes" returned?
@EOS good point. Only return yes if you've reached a leaf node (left and right are both null.) Fixed. The idea is that you only know about your node. You know if your node fails, so you can return no and have it propagate up. You know if you have no children under you, so you can return yes and let it propagate up. Otherwise, you have to look down to see what's going on.
One mention:to match with most programming languages, instead of "no" , to return 0.Thus, the program maintains its validity both as an idea and also as a possible implementation.
1

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 [...]"

Improve this answer

2 Comments

You used though boolean variables in your solution, so it works well in the first test.But with "yes" , I would also have to test for it in the first return, right?
@EOS I used booleans because the function has to be able to do boolean algebra: it has to combine the return of its children into one result. booleans make this easier.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.