Find the size of a binary tree

You're in an Oracle interview, and the interviewer draws a tree on the whiteboard with five nodes scattered across three levels. "How many nodes does this tree have?" they ask. You count them visually - five. Then comes the real question: "Now write a function that does that counting for any binary tree." This problem, also known as "Count Nodes in Binary Tree" on other platforms, is one of the cleanest introductions to recursive thinking on trees. It tests whether you can decompose a tree problem into subproblems and combine results, a skill that transfers directly to dozens of harder tree questions.

TL;DR

Count nodes recursively: if the root is null, return 0. Otherwise, return 1 + size(root.left) + size(root.right). Every node gets visited once for O(n) time, and the call stack grows to the tree's height for O(log n) space in a balanced tree. The pattern is almost identical to finding tree height, but uses addition instead of max.

Why This Problem Matters

Finding the size of a binary tree is the simplest recursive tree problem you can encounter, which makes it the perfect entry point for understanding how recursion maps onto tree structures. Once you internalize this "1 + left + right" pattern, problems like finding height, checking balance, calculating diameter, and summing paths all follow the same template. Companies like Oracle and Cisco use it as a warm-up to gauge whether candidates can think recursively before moving to harder tree manipulation questions.

Binary Trees: A Quick Refresher

A binary tree is a hierarchical data structure where each node holds a value and has at most two children, referred to as the left child and the right child.

Key terminology:

• Root: The topmost node (node 1 in our example)
• Leaf: A node with no children (nodes 2, 4, and 5 above)
• Size: The total count of all nodes in the tree
• Subtree: Any node and all its descendants form a subtree

The tree above has 5 nodes total. Node 2 is a leaf on the left, while node 3 has its own subtree of size 3 (nodes 3, 4, and 5).

Understanding the Problem

Given: The root node of a binary tree Return: The total number of nodes in the tree Convention: An empty tree (null root) has size 0

Here is the example from the problem definition:

tree: 1 2 3 # # 4 5

    1
   / \
  2   3
     / \
    4   5

size(1 2 3 # # 4 5) -> 5

The # symbols represent null children, so node 2 has no left or right child.

Edge Cases to Consider

1. Empty tree (null root): Size = 0
2. Single node: Size = 1
3. Skewed tree (all nodes on one side): Size equals the chain length
4. Perfect binary tree: Size = 2^h - 1 where h is the height

A single node is its own root and leaf simultaneously, so the size is 1.

Solution Approach

Think about this problem from any node's perspective. If you're a node, how many nodes exist in "your" tree? It's yourself (1 node) plus however many nodes are in your left subtree, plus however many are in your right subtree. That's the entire algorithm.

Building the Recursive Insight

Imagine you're standing at the root, and you send two assistants down the tree. One goes left, one goes right. Each assistant does the same thing at their node: counts themselves, then sends their own assistants further down. When an assistant reaches a spot with no node (null), they report back "zero." The reports bubble up, and you add them all together.

For our example tree:

• Node 2 reports: "I have 1 node (just me)."
• Node 4 reports: "I have 1 node."
• Node 5 reports: "I have 1 node."
• Node 3 collects reports: "1 (me) + 1 (left) + 1 (right) = 3 nodes."
• Node 1 collects reports: "1 (me) + 1 (left child 2) + 3 (right subtree) = 5 nodes."

This naturally decomposes into a recursive formula:

size(node) = 0                                    if node is null
size(node) = 1 + size(node.left) + size(node.right)   otherwise

Implementation

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

public class Solution {
  public int size(TreeNode root) {
    // Base case: an empty tree has size 0
    if (root == null) {
      return 0;
    }

    // Count this node (1) plus all nodes in left and right subtrees
    return 1 + size(root.left) + size(root.right);
  }
}

Two lines of logic. That's it. The elegance here is not accidental. Trees are recursive data structures, so recursive solutions map onto them naturally.

Tracing Through the Example

Let's watch the recursion unfold on our example tree:

The recursion visits every node in a depth-first order. At each leaf, the two recursive calls hit null and return 0 immediately. The leaf then returns 1 + 0 + 0 = 1. These values propagate upward until the root assembles the final count.

Detailed call trace:

Complexity Analysis

Time Complexity: O(n)

Every node is visited exactly once. At each node, we do a constant amount of work: one comparison, one addition, and two recursive calls. The total work scales linearly with the number of nodes.

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

The space cost comes entirely from the recursive call stack. Each active call occupies one stack frame, and the maximum number of simultaneous frames equals the depth of the deepest recursive path, which is the tree's height.

For a balanced tree, the height is O(log n), so the stack uses O(log n) space:

For a skewed tree where every node has only one child, the height equals n, and the stack grows to O(n):

This worst-case scenario is worth mentioning in an interview. It shows you understand that recursion depth depends on tree shape, not just node count.

Common Pitfalls

1. Forgetting the base case: Without the null check, your code crashes with a NullPointerException on the very first leaf's children. Every tree recursion needs this guard.

2. Returning 0 for a single node: Some candidates accidentally return 0 instead of 1 when the node has no children. The base case handles null, not "leaf." A leaf node still counts as 1.

3. Confusing size with height: Size adds subtree sizes (left + right), while height takes the maximum (max(left, right)). Mixing these up gives wrong results for unbalanced trees.

4. Trying an iterative approach first: While you can solve this iteratively with a queue, the recursive solution is cleaner and what interviewers expect for this problem. Save the iterative approach for when space complexity is the primary concern.

Interview Tips

When solving this problem in an interview:

1. Start by clarifying: "Should I count the total number of nodes? And an empty tree returns 0?" This takes five seconds and prevents misunderstandings.

2. State the recursive structure: "Each node contributes 1 to the count, plus the sizes of its two subtrees. Null returns 0." Saying this before writing code shows structured thinking.

3. Write the code: It's two lines. Don't overthink it. The simplicity is the point.

4. Analyze complexity: "O(n) time because we visit every node. O(log n) space for a balanced tree due to the call stack, O(n) in the worst case for a skewed tree."

5. Anticipate follow-ups:

   • "How would you do this iteratively?" Use BFS with a queue.
   • "What if you needed to count nodes at a specific level?" Modify the recursion to track depth.
   • "How would you check if the tree is complete?" Compare size against 2^height - 1.

Comparing Size and Height

Since finding tree height is a closely related problem, here's how the two patterns compare side by side:

Once you see this pattern, you realize that many tree problems are just variations on the same recursive skeleton with different combining operations.

Key Takeaways

• The recursive formula 1 + size(root.left) + size(root.right) with a null base case returning 0 solves tree size in two lines.
• Time complexity is O(n) since every node must be visited. Space complexity is O(h) where h is the tree height, ranging from O(log n) for balanced trees to O(n) for skewed trees.
• This "decompose into subtrees, combine results" pattern is the foundation for tree height, diameter, balance checking, and path sum problems. Learning it here pays dividends across your entire interview prep.
• Always mention the skewed-tree worst case for space complexity. It signals to interviewers that you understand recursion depth depends on tree shape.
• For an iterative alternative, use BFS with a queue and a counter. Both approaches run in O(n) time, but the recursive version is cleaner and expected for this difficulty level.

Practice Makes Perfect

Once you're comfortable counting nodes, try these related problems to strengthen your recursive tree skills:

• Find the height of a binary tree (swap addition for max)
• Find the minimum depth of a binary tree
• Check if a binary tree is balanced
• Count the number of leaf nodes

These all follow the same recursive skeleton. Consistent practice with these patterns is the fastest way to build confidence for technical interviews. This problem and hundreds of others are available on Firecode, where over 50,000 users have prepared for interviews and landed roles at top tech companies.

Solutions in Other Languages

Python

class Solution:
    def size(self, root: TreeNode) -> int:
        if root is None:
            return 0
        return 1 + self.size(root.left) + self.size(root.right)

JavaScript

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

TypeScript

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

C++

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

Go

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

Scala

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

Kotlin

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

Rust

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

Swift

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

Dart

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

Ruby

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

C#

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

PHP

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