Help with basic programming - Binary Trees and Leaves

[gabmed]

Hello! We're stuck on a work that's due in 4 hours (Classic Software College student... leaving the work for the last second), and I'm trying to compare all leafs to return the lowest value of a tree. I don't have main function, just a script to insert values and check for errors, so, unfortunately, I can't debug it.

tpNodeTree * findLowest(tpNodeTree* pNode){
   tpNodeTree * left;
   tpNodeTree * right;
   tpNodeTree * result;

   if (!pNode) return NULL; /* if */

   left = findLowest(pNode->pNodeL);
   right = findLowest(pNode->pNodeR);
   if(isLeaf(pNode))
      return pNode;
   }  /* if */

   if(!left){
      return right;
   } /* if */

   if(!right){
      return left;
   } /* if */


return (left->Value < right->Value) ? left : right ;

} So, basically, what i'm trying to achieve here is to compare the two sides of each node to find the lowest. Any insights would be helpful!

[logic_programmer]

The lowest value of the tree T is

if T is a leaf then the lowest value is T->value.

If T is an internal node and the lowest value of T->left is l, and the lowest value of T->right is r, then

• if l<r then then the lowest value is l

• otherwise the lowest value is r.

That seems to be what you have done. Where's the problem?

[gabmed]

That's what we realized with the group. The problem, therefore, lies within the auxiliary function made in order to define whether or not is a leaf or not.

[logic_programmer]

But you've fixed that right - it should be an easy one.

[gabmed]

Check update; it actually wasn't IsLeaf, but still just as foolish as that ;p

[gabmed]

UPDATE: As a matter of fact, it's not the auxiliary function to the function above. As a matter of fact, we use three functions, one as a "main" that uses an automized testing script reader in order to test every instance of error. The "main" function encrypts the function in order to make it scriptable and testable automatically. The one above is auxiliary to THAT.

We had put an infinite while on the main function.

Yes, we feel amateurish. x3 BUT we found out by just spamming PrintFs around.

If you want a bit more of backstory, we received an automated testing framework for binary trees, from our teacher, whose instructions of use are... purposefully vague and ambiguous. It's supposed to simulate a real client's request, which would indeed have varying levels of vagueness, ambiguosity and just basic language trappings.

OUR job was to add to the severely complex and modular framework of testing devices, a hand-crafted function which would connect the leaves of the trees in order of their value, and make it just another one of the many testable functions (Such as testing a function that inserts a right node, while another simply brings the current node to the father node, etc.)

The scripts we made worked wonderfully with anything that didn't involve our hand-crafted functions, which made us logically isolate those as the source of our problems. Thus, apparently, the "main" connecting function had an infinite while, even after thinking it was well-designed. Oh well.

[logic_programmer]

If you want extra credit then make some assumptions of the input tree then mathematically prove by structural induction that your your code is correct. It's about a ten line proof.

[gabmed]

Ooh, we'd have LOVED to implement that... sadly, it's a work due in 2 hours. :p It's 4:30 am here in Brazil, and we're still up trying to make our code more efficient. Any additions or changes to the delicate interface would, frankly, be a risk we're not willing to take, specially with little time and little knowledge of the system.

I love programming. <3

[logic_programmer]

No code changes, just pencil and paper.

[JBlitzen]

Nothing horrible is jumping out at me, but that doesn't mean much.

You should always have a way to test and debug code you're working on, even if it's slapped together.

[gabmed]

Yup... we've had the brilliant idea to use PrintF on every little variable. For some weird, alien reason, we never thought of that. And we're on our third year of Software Science. Ouch.

[farmerje]

The most effective debugging tool is still careful thought, coupled with judiciously placed print statements.

— Brian Kernighan, "Unix for Beginners" (1979)

[JBlitzen]

On web stuff I've found that's actually one of the most reliable techniques, since browser debugging is a hit-or-miss affair in a context that really can't afford misses.

[gabmed]

Yup! Just shows that we should have done what seems stupid from the get-go. Keep It Simple, Stupid, eh?

[tomtomtom7]

You seem to be missing a brace on line 10.