Count the leaves of a binary tree

You're in a Facebook phone screen, and the interviewer pulls up a shared editor. "Given a binary tree," they say, "count how many leaf nodes it has." It sounds almost too simple at first, but this question is a litmus test for how well you understand recursive tree traversal. It also happens to be one of the most common warm-up problems at companies that lean heavily on tree-based data structures. This problem is also known as "Count Leaf Nodes in Binary Tree" on other platforms.

TL;DR

Count leaf nodes by recursing through the tree with three cases: return 0 for null, return 1 for a node with no children, and sum the results of left and right subtrees for internal nodes. This visits every node once for O(n) time and uses O(log n) stack space on a balanced tree. The key distinction from tree height or size is that you only count nodes where both left and right are null.

Why This Problem Matters

Counting leaf nodes teaches the foundational pattern of tree recursion: decompose, solve subproblems, combine. It is the simplest problem that requires you to distinguish between leaf nodes and internal nodes, a skill that directly transfers to harder problems like finding the boundary of a binary tree, summing leaf values, or checking whether two trees share the same leaf sequence. Get this one down, and the more complex variations become straightforward extensions.

Binary Trees: A Quick Refresher

A binary tree is a hierarchical structure where each node has at most two children. The topmost node is the root, and nodes with no children are called leaves. Every subtree is itself a valid binary tree, which is exactly what makes recursion so natural for tree problems.

In the tree above, node 1 is the root. Node 3 is an internal node because it has children. Nodes 2, 4, and 5 are leaves because neither has any children.

Understanding the Problem

Given: The root of a binary tree Return: The number of leaf nodes (nodes with no children) Constraint: The tree contains at most 100 nodes

Here is our example tree with the leaf nodes labeled:

Three nodes have no children: 2, 4, and 5. So numLeaves(root) returns 3.

Prefer a different language? Jump to solutions in other languages.

Edge Cases

1. Empty tree (null root): Return 0
2. Single node: The root is both the root and the only leaf, so return 1
3. Skewed tree (all nodes on one side): Only the bottommost node is a leaf
4. Full binary tree: Every internal node has exactly two children, so roughly half the nodes are leaves

A single-node tree is worth pausing on. Since the root has no children, it qualifies as a leaf:

Solution Approach

Think about what it means to count leaves from the perspective of a single node. You are standing at some node and need to report how many leaves exist in the subtree rooted at that node. Three things can happen:

1. The node does not exist (null). There are zero leaves here.
2. The node exists but has no children. This node is itself a leaf. Report 1.
3. The node has at least one child. It is not a leaf. Ask your left subtree and your right subtree how many leaves they contain, and add those two numbers together.

That is the entire algorithm. Each node delegates the counting to its children until it reaches the base cases.

Why This Works

The recursion bottoms out at null pointers, which return 0 and stop further calls. Leaf nodes return 1 without recursing further. Internal nodes simply aggregate. Since every node is visited exactly once and performs constant work, the total time is proportional to the number of nodes.

Building Intuition with a Larger Tree

Consider a perfect binary tree with seven nodes:

Starting at node 1, we ask nodes 2 and 3 for their leaf counts. Node 2 has no children, so it reports 1. Node 3 asks nodes 6 and 7. Both are leaves and each reports 1. Node 3 sums them: 1 + 1 = 2. Back at node 1: 1 + 2 = 3. But wait, nodes 4 and 5 are also children of node 2 in this tree. Let me correct that. In a full binary tree with 7 nodes, node 2 has children 4 and 5 (both leaves), so node 2 reports 2. Node 3 has children 6 and 7 (both leaves), so node 3 reports 2. Node 1 sums them: 2 + 2 = 4 leaves total. This matches what we see: the four bottom nodes are all leaves.

Implementation

Here is the Java solution:

public class Solution {
  public int numLeaves(TreeNode root) {
    // Base case: null node contributes zero leaves
    if (root == null) return 0;

    // Leaf node: no children means this node is a leaf
    if (root.left == null && root.right == null) return 1;

    // Internal node: sum leaves from both subtrees
    return numLeaves(root.left) + numLeaves(root.right);
  }
}

Three lines of logic. That is what makes this problem satisfying. The code maps directly to the three cases we discussed.

Tracing Through the Example

Let's watch the recursion unfold on our example tree (1 2 3 # # 4 5):

The call stack builds up as we go left first (depth-first), then backtracks and goes right. Each leaf returns 1, each internal node sums its children's results, and the root collects the final answer: 3.

Complexity Analysis

Time Complexity: O(n)

Every node is visited exactly once. At each node we do a constant amount of work: check for null, check for leaf, or make two recursive calls. The total work across all nodes is O(n).

Space Complexity: O(log n) average, O(n) worst case

The space comes entirely from the call stack. In a balanced tree, the maximum recursion depth is the height of the tree, which is O(log n). In the worst case of a completely skewed tree where each node has only one child, the depth equals n:

This skewed tree has 4 nodes but only 1 leaf (node 4). The recursion depth is 4, matching the number of nodes. In an interview, always mention this worst-case scenario to show you have thought about degenerate inputs.

Common Pitfalls

1. Forgetting the null check: Without if (root == null) return 0, you will get a null pointer exception on any tree that is not perfectly full.

2. Confusing with tree size: The tree size formula 1 + numLeaves(root.left) + numLeaves(root.right) counts all nodes. Leaf counting skips the +1 for internal nodes and only returns 1 for actual leaves.

3. Adding 1 at every level: A common mistake is writing return 1 + numLeaves(root.left) + numLeaves(root.right) by analogy with the height problem. This counts all nodes, not just leaves.

4. Missing the single-child case: If a node has one child and one null, it is not a leaf. The null side returns 0, and the recursive call on the non-null side handles the subtree correctly. No special case is needed because the general recursive case already covers it.

Interview Tips

When you get this problem in an interview:

1. Clarify definitions: Ask whether an empty tree should return 0 or if it is guaranteed to be non-empty. Ask whether a single node counts as a leaf (it does).

2. Start with the three cases: Write out the base cases and recursive case before coding. This makes the implementation nearly automatic.

3. Trace a small example: Use the example tree from the problem (5 nodes, 3 leaves) and walk through the recursion. Interviewers like seeing you verify your logic before submitting.

4. Mention the iterative alternative: You could use BFS with a queue and count nodes where both children are null. The time complexity stays O(n), but the space becomes O(w) where w is the maximum tree width. Mentioning this tradeoff shows breadth of knowledge.

5. Connect to harder problems: If the interviewer asks for follow-ups, mention summing leaf values, finding the leftmost leaf, or checking if two trees have identical leaf sequences. These all build on the same pattern.

Key Takeaways

• The recursive formula has three cases: return 0 for null, return 1 for a leaf, and sum left + right for internal nodes. This visits every node exactly once for O(n) time.
• Space complexity depends on tree shape: O(log n) for balanced trees, O(n) for skewed trees. Always mention the worst case in interviews.
• Leaf counting differs from height and size by only counting nodes where both children are null, not adding 1 for every node visited.
• A single node is both the root and a leaf. An empty tree has zero leaves. Nail these edge cases before writing code.
• This problem's three-case recursive pattern is the building block for harder tree problems like boundary traversal, leaf-similar trees, and sum of left leaves.

Related Problems and Practice

Once you are comfortable counting leaves, try these related problems to build on the same recursive pattern:

• Find the height of a binary tree (similar recursion, different combination step)
• Find the size of a binary tree (count all nodes instead of just leaves)
• Check if a binary tree is balanced (compare left and right heights)
• Sum of left leaves (count only leaves that are left children)

This problem and hundreds of other tree problems are available on Firecode, where over 50,000 engineers have prepared for technical interviews. Whether you are warming up for a phone screen or grinding through tree problems before an onsite, building fluency with these recursive patterns is what separates solid candidates from great ones.

Solutions in Other Languages

Python

class Solution:
    def num_leaves(self, root):
        if root is None:
            return 0
        if root.left is None and root.right is None:
            return 1
        return self.num_leaves(root.left) + self.num_leaves(root.right)

JavaScript

class Solution {
  numLeaves(root) {
    if (root === null) return 0;
    if (root.left === null && root.right === null) return 1;
    return this.numLeaves(root.left) + this.numLeaves(root.right);
  }
}

TypeScript

class Solution {
  numLeaves(root: TreeNode | null): number {
    if (root === null) return 0;
    if (root.left === null && root.right === null) return 1;
    return this.numLeaves(root.left) + this.numLeaves(root.right);
  }
}

C++

class Solution {
public:
  int numLeaves(TreeNode *root) {
    if (root == nullptr) return 0;
    if (root->left == nullptr && root->right == nullptr) return 1;
    return numLeaves(root->left) + numLeaves(root->right);
  }
};

Go

func (s *Solution) NumLeaves(root *TreeNode) int {
    if root == nil {
        return 0
    }
    if root.Left == nil && root.Right == nil {
        return 1
    }
    return s.NumLeaves(root.Left) + s.NumLeaves(root.Right)
}

Scala

class Solution {
  def numLeaves(root: TreeNode): Int = {
    if (root == null) 0
    else if (root.left == null && root.right == null) 1
    else numLeaves(root.left) + numLeaves(root.right)
  }
}

Kotlin

class Solution {
  fun numLeaves(root: TreeNode?): Int {
    if (root == null) return 0
    if (root.left == null && root.right == null) return 1
    return numLeaves(root.left) + numLeaves(root.right)
  }
}

Swift

class Solution {
    func numLeaves(_ root: TreeNode?) -> Int {
        if root == nil { return 0 }
        if root!.left == nil && root!.right == nil { return 1 }
        return numLeaves(root!.left) + numLeaves(root!.right)
    }
}

Rust

impl Solution {
    pub fn num_leaves(&self, root: Option<Box<TreeNode>>) -> i32 {
        if root.is_none() {
            return 0;
        }
        let node = root.unwrap();
        if node.left.is_none() && node.right.is_none() {
            return 1;
        }
        self.num_leaves(node.left) + self.num_leaves(node.right)
    }
}

Ruby

class Solution
  def num_leaves(root)
    return 0 if root.nil?
    return 1 if root.left.nil? && root.right.nil?
    num_leaves(root.left) + num_leaves(root.right)
  end
end

Dart

class Solution {
  int numLeaves(TreeNode? root) {
    if (root == null) return 0;
    if (root.left == null && root.right == null) return 1;
    return numLeaves(root.left) + numLeaves(root.right);
  }
}

C#

public class Solution {
    public int numLeaves(TreeNode? root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return 1;
        return numLeaves(root.left) + numLeaves(root.right);
    }
}

PHP

class Solution {
    public function numLeaves(?TreeNode $root): int {
        if ($root === null) return 0;
        if ($root->left === null && $root->right === null) return 1;
        return $this->numLeaves($root->left) + $this->numLeaves($root->right);
    }
}