Count the Leaves of a BST

Complete the private helper countLeaves(Node node) so that countLeaves() returns how many leaves the tree has.

Reminder: leaves and internal nodes. A leaf is a node with no children at all: both left and right are null. Every other node is an internal node. In a BST the leaves form the bottom edge of the tree, and a newly inserted value always starts out as a leaf.

      8
     / \
    3   10
   / \    \
  1   6    14

In this tree 1, 6 and 14 are leaves. 8, 3 and 10 are not, because each has at least one child (10 has only a right child, which is enough).

The recursion has the same shape as counting all the nodes, with one extra case in the middle: an empty subtree has 0 leaves, a node with no children is exactly 1 leaf, and any other node has as many leaves as its two subtrees put together.

Requirements: 1. Return 0 when node is null. 2. Return 1 when node has no left child and no right child. 3. Otherwise return the leaves of the left subtree plus the leaves of the right subtree. 4. Use recursion.

The Node class is provided - do not rename it and do not add public to it, because a Java source file may contain only one public class.

Do NOT write a main method.