Count the number of leaves in a binary tree

Objective: Given the root pointer to a binary tree, find the number of leaves. In the binary tree given below, number of leaf nodes of 4.

Solution: Leaf has property that its left and right child both are null. Using this property we can recurse the tree from root node towards bottom moving to left and right branches and keep counting those nodes which has both the children as null. 

Time Complexity: O(n) where n is number of nodes in the tree.

Java Solution:

       
public class CountNoOfLeaves {

    public static void main(String[] args) throws Exception {
        //Build Tree        
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node7 = new Node(7);
        Node node9 = new Node(9);
        node1.left = node2;
        node1.right = node3;
        node2.left = node7;
        node2.right = node9;
        node3.left = node5;
        node3.right = node4;
        System.out.println(numLeaves(node1));
    }


    private static int numLeaves(Node root){
        if(root == null){
            return 0;
        }

        if(root.left == null && root.right == null){
            return 1;
        }

        return numLeaves(root.left) + numLeaves(root.right);
    }

    static class Node {
        int data;
        Node left;
        Node right;

        Node(int data) {
            this.data = data;
        }
    }

}