Problem

Count leaf nodes in a binary tree

Examples

Example 1:

1
2
3
4
5

   3
  / \
 9   20
    /  \
   15   7

1
2

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

Solution

Method 1 - Iterative using stack

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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);
	}
}