Number of binary trees Number of sheets

Question

Suppose you already have the basic binary procedures: empty (bt), root (bt), left (bt) and right (bt). Write an isLeaf (bt) procedure 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 fix it?

Answer 1

You don’t know anything unless you try to solve it yourself, but simply for people who come here to look for the 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)); } 

Answer 2

The main idea here is to use recursion:

The number of leaves a node has the sum of the number of leaves left by his left child, and the number of leaves has his right child.

Answer 3

As @jeffrey greenham said, we can use recursion

 int countleaves(struct node* root){ if(root!=null) { countleaves(root->left); if(root->left==NULL&&root->right==NULL) { count++; } countleaves(root->right); } }