Count Number of Leaf Nodes in Binary Tree

Problem

Count leaf nodes in a binary tree

Examples

Example 1:

   3
  / \
 9   20
    /  \
   15   7

Input: root = [3,9,20,null,null,15,7]
Output: 2

Solution

Method 1 - Iterative using stack

Code

Java
public int countLeafNodes(TreeNode root) {
	if (root == null) {
		return 0;
	}

	Stack stack = new Stack<>();
	stack.push(root);
	int count = 0;

	while (!stack.isEmpty()) {
		TreeNode node = stack.pop();

		if (node.left != null) {
			stack.push(node.left);
		}

		if (node.right != null) {
			stack.push(node.right);
		}
		// found the leaf
		if (node.left == null && node.right == null) {
			count++;
		}

	}

	return count;

}

Method 2 - Recursive

Code

Java
public int countLeafNodes(TreeNode root) {
	return countLeaves(root);
}


private int countLeaves(TreeNode node) {
	if (node == null)
		return 0;

	if (node.left == null && node.right == null) {
		return 1;
	} else {
		return countLeaves(node.left) + countLeaves(node.right);
	}
}