Binary Tree: Count Leaves

Binary Tree: Count Leaves

Insert the integers into a BST in input order, then complete countLeaves to return the number of leaf nodes.

A leaf is a node whose left AND right children are both NULL.

Pitfall: testing only t->left == NULL wrongly treats a node with only a right child (e.g. 70 below) as a leaf. Both children must be NULL.

Input

• Line 1: integer n.
• Line 2: n space-separated integers, inserted in this order.

Output

• One line: the number of leaves.

Example: input 6 / 50 30 70 20 40 80 → output 3 (leaves are 20, 40, 80; node 70 has a right child so it is not a leaf).