Count the leaves of a binary tree and measure its height with two short recursive functions.
What to build
Two recursive functions on a binary tree that the starter has already built.
Requirements
leavesreturns the number of nodes that have no children.heightreturns the number of levels: a tree with one node has height 1.- Print the two results on one line.
Input
The first line has n. Line i of the next n lines describes node i: its value, then the numbers of its left and right children, or -1 for no child. Node 0 is the root.
Output
One line: the number of leaves and the height.
Constraints
1 ≤ n ≤ 100.
Example
Input:
5
1 1 2
2 3 4
3 -1 -1
4 -1 -1
5 -1 -1
Output:
3 3
Why it works
Both answers for a tree follow from the answers for its two subtrees, so each function is a base case and one line that combines two recursive calls.
Examples
5 1 1 2 2 3 4 3 -1 -1 4 -1 -1 5 -1 -1
3 3
1 9 -1 -1
1 1
Hints
Hint 1
An empty tree has 0 leaves and height 0.
Hint 2
A node with no children is a leaf: it counts as 1.
Hint 3
Otherwise the leaves are those of the left subtree plus those of the right, and the height is 1 more than the taller subtree.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
#include <stdlib.h>
typedef struct tree {
int value;
struct tree *left, *right;
} Tree;
int leaves(Tree *t) {
if (t == NULL) return 0;
if (t->left == NULL && t->right == NULL) return 1;
return leaves(t->left) + leaves(t->right);
}
int height(Tree *t) {
if (t == NULL) return 0;
int l = height(t->left), r = height(t->right);
return 1 + (l > r ? l : r);
}
int main(void) {
int n;
scanf("%d", &n);
Tree *nodes[100];
for (int i = 0; i < n; i++) nodes[i] = malloc(sizeof(Tree));
for (int i = 0; i < n; i++) {
int l, r;
scanf("%d %d %d", &nodes[i]->value, &l, &r);
nodes[i]->left = l == -1 ? NULL : nodes[l];
nodes[i]->right = r == -1 ? NULL : nodes[r];
}
printf("%d %d\n", leaves(nodes[0]), height(nodes[0]));
for (int i = 0; i < n; i++) free(nodes[i]);
return 0;
}