CODEWITHSUNDEEP
algorithmrecursionbinary-treepseudocode
EOS
EOS

Reputation: 15

Binary tree recursive problem

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!

Upvotes: 1

Views: 1043

Answers (3)

Jerry Coffin
Jerry Coffin

Reputation: 490108

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

Upvotes: 3

corsiKa
corsiKa

Reputation: 82559

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

Upvotes: 1

vlad
vlad

Reputation: 4778

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

Upvotes: 1

Related Questions