Binary Trees Count Number of Leaves

Question

Suppose you already have the basic binary tree procedures isempty(bt), root(bt), left(bt), and right(bt). Write a procedure isLeaf(bt) that returns true if the binary tree bt is a leaf node and false if it is not.

This is what I have:

proc isLeaf(bt)
if (isEmpty(bt))
error('The binary tree is empty.');
elseif (left(bt) < right(bt))
return true;
else return false;

Then write a procedure numLeaves(bt) that returns the number of leaves in the binary tree bt.

This is what I have:

proc numLeaves(bt)
if (isEmpty(bt))
error ('The binary tree is empty.');
elseif (count left(bt) + right(bt));
return (left(bt) + right(bt);

please could you correct?

This looks like a homework question. If so, please follow the guidelines for asking homework questions on StackOverflow, as well as Jon Skeet's guidelines on asking the perfect question. Lastly, when asking a question you should always say what you expect to happen and what actually happens. Otherwise, we can only guess at what you want or mean. Right now, my guess is you want your functions to be friendlier. — outis
This doesn't look like Java code - is it pseudocode? Please post the actual code you're having trouble with. — bdonlan
Surely if it's a leaf node then there are no left or right nodes? The isLeft(bt) functionality looks like the sort function you'd use to organize the tree. — trojanfoe

Jordi Jordi · Accepted Answer · 2011-02-08T12:41:58

You'll learn very little to nothing if you don't try to solve this yourself, but just for people coming here looking for an answer:

boolean isLeaf (BinaryTree bt) {
    return !isempty(bt) && isempty(left(bt)) && isempty(right(bt));
}

int numLeaves (BinaryTree bt) {
    if (isempty(bt))
        return 0;
    else if (isLeaf(bt))
        return 1;
    else
        return numLeaves(left(bt)) + numLeaves(right(bt));
}

Binary Trees Count Number of Leaves

3 Answers