Sum all nodes of a binary tree without recursion

You're working through a technical screen and the interviewer pulls up a binary tree on the shared editor. "Sum every node in this tree," they say, "but you can't use recursion." The twist catches a lot of candidates off guard. Recursion is the default tool for tree problems, and taking it away forces you to think about what recursion actually does under the hood. This problem, sometimes listed as "Binary Tree Sum Iterative BFS" on other platforms, tests whether you can replace implicit stack frames with an explicit data structure.

TL;DR

Use a queue-based breadth-first search (BFS). Initialize a sum to 0, enqueue the root, and loop: dequeue a node, add its value to the sum, enqueue its non-null children. When the queue is empty, return the sum. This runs in O(n) time and O(n) space in the worst case. The entire solution is about 10 lines of code.

Why This Problem Matters

Summing nodes without recursion is a gateway problem for iterative tree traversal. Once you've internalized the queue-based BFS pattern, you can apply it to level-order traversal, finding the maximum node, counting leaves, and dozens of other tree problems. Interviewers at companies like Google and Amazon frequently build on this pattern in follow-up questions, so having it in muscle memory pays dividends.

Binary Trees and BFS: A Quick Refresher

A binary tree is a hierarchical structure where each node has at most two children. When we talk about visiting every node, there are two broad strategies: depth-first (DFS), which dives down one branch before backtracking, and breadth-first (BFS), which sweeps across each level before moving deeper.

In the tree above, BFS visits nodes in this order: 1, 2, 3, 4, 5. It processes the root first, then all nodes at depth 1, then all nodes at depth 2, and so on. A queue naturally enforces this ordering because nodes enqueued first are dequeued first (FIFO).

Understanding the Problem

Here is what we need to accomplish:

Given: The root of a binary tree Return: The sum of all node values Constraint: No recursion allowed Edge case: An empty tree (null root) should return 0

For the example tree 1 2 3 # # 4 5:

The sum is 1 + 2 + 3 + 4 + 5 = 15. The order in which we visit the nodes does not matter for the final sum since addition is commutative. But using a queue gives us a clean, predictable traversal pattern that is easy to reason about during an interview.

Edge Cases to Consider

1. Empty tree (null root): Return 0 immediately
2. Single node: The sum equals that node's value
3. Skewed tree (all nodes on one side): Still works, the queue just never holds more than one node
4. Large values: Depending on the language, watch for integer overflow on very large trees

Solution Approach

The idea is straightforward. Recursion visits every node by pushing frames onto the call stack. Without recursion, we need our own data structure to track which nodes still need processing. A queue works perfectly for this.

The Algorithm

1. If the root is null, return 0
2. Create a queue and enqueue the root
3. While the queue is not empty:
   • Dequeue the front node
   • Add its data to the running sum
   • If its left child exists, enqueue it
   • If its right child exists, enqueue it
4. Return the sum

Here is how the queue evolves step by step for our example tree:

Each step polls one node from the front of the queue and potentially adds two children to the back. The sum accumulates as we go. When the queue empties, every node has been visited exactly once.

Why a Queue and Not a Stack?

You could absolutely use a stack instead. With a stack you get a DFS traversal (similar to pre-order), and the final sum would be identical. The queue-based approach is more common in interviews for this class of problem because the level-by-level processing is easier to trace on a whiteboard. That said, if an interviewer asks for a stack-based variant, the only change is swapping queue.offer / queue.poll with stack.push / stack.pop.

Implementation

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

import java.util.Deque;
import java.util.LinkedList;

public class Solution {
  public int sumNodes(TreeNode root) {
    int sum = 0;
    if (root == null) return sum;

    Deque<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
      TreeNode node = queue.poll();
      sum += node.data;

      if (node.left != null) queue.offer(node.left);
      if (node.right != null) queue.offer(node.right);
    }

    return sum;
  }
}

Let's walk through the execution for the tree 1 2 3 # # 4 5:

Iteration 1: Dequeue node 1 (sum = 1). Enqueue 2 and 3. Iteration 2: Dequeue node 2 (sum = 3). No children. Iteration 3: Dequeue node 3 (sum = 6). Enqueue 4 and 5. Iteration 4: Dequeue node 4 (sum = 10). No children. Iteration 5: Dequeue node 5 (sum = 15). Queue is empty. Return 15.

The loop runs exactly once per node in the tree. No node is visited twice, no node is skipped.

Complexity Analysis

Time Complexity: O(n)

Every node is enqueued once and dequeued once. The work per node is constant: one addition and up to two enqueue operations. Total work scales linearly with the number of nodes.

Space Complexity: O(n)

The queue holds at most one full level of the tree at any point. For a balanced binary tree, the widest level is the last one, which contains roughly n/2 nodes:

In this balanced tree, level 2 has 4 nodes out of 7 total. The queue would hold all 4 simultaneously when processing level 1. That makes the worst-case space O(n).

For a completely skewed tree, however, each level has exactly one node, so the queue never exceeds size 1:

This is the best case for space, but we still describe the overall space complexity as O(n) because algorithm analysis uses the worst case.

Iterative vs. Recursive Space Trade-offs

This is worth mentioning in an interview because it shows deeper understanding:

The two approaches trade off in opposite directions. BFS uses more space on wide trees, DFS uses more space on deep trees. For a balanced tree, the recursive approach wins on space. For a skewed tree, the iterative approach wins. Neither dominates in all cases.

Common Pitfalls

1. Forgetting the null check: If you try to enqueue a null root, you'll get a NullPointerException on the first queue.poll().data call. Always guard with if (root == null) return 0.

2. Enqueuing null children: If you skip the null check on children, you'll enqueue null values and crash on the next iteration. Always check if (node.left != null) before enqueuing.

3. Using the wrong end of the queue: In Java, offer adds to the tail and poll removes from the head. Mixing these up turns your queue into something unpredictable. If you use a Deque, stick with offer/poll (or addLast/removeFirst).

4. Returning the wrong variable: Make sure you return sum, not root.data or some other intermediate value. It sounds obvious, but under interview pressure, these slip-ups happen.

Interview Tips

When solving this in a live interview:

1. Clarify the constraint: Ask "When you say no recursion, do you mean I should use an iterative approach with an explicit data structure?" This shows you understand what the constraint is really testing.

2. State your approach upfront: "I'll use a queue-based BFS to visit every node and accumulate the sum. This gives O(n) time and O(n) space."

3. Trace through a small example: Pick 3-5 nodes and show the queue state at each step. Interviewers love seeing candidates verify their logic before coding.

4. Mention the stack alternative: "I could also use a stack for DFS traversal. The sum would be the same since addition is order-independent. I'll go with the queue since BFS is more natural for level-order problems."

5. Handle follow-ups: Be ready for "What if I wanted the sum per level?" (track queue size at each level), "What about the maximum node?" (replace sum with max), or "Can you do this with O(1) extra space?" (Morris traversal, though that's an advanced topic).

Key Takeaways

• The queue-based BFS pattern for iterative tree traversal is: enqueue root, then loop (dequeue, process, enqueue children). This template works for summing, counting, finding max/min, and level-order traversal.
• Both BFS (queue) and DFS (stack) produce the correct sum since addition is commutative. BFS is the conventional choice for interview settings because the level-by-level processing is easier to trace.
• Space complexity depends on tree shape: O(n) for balanced trees (wide levels), O(1) for skewed trees (one node per level). Interviewers appreciate hearing this nuance.
• Always handle the null root edge case first. It prevents null pointer exceptions and keeps the main logic clean.
• This problem is a stepping stone. Once you have the BFS loop memorized, adapting it for level-order traversal, tree width, or per-level aggregation is a matter of swapping out the processing step inside the loop.

Practice Makes Perfect

If you found this problem approachable, try these related challenges to strengthen your iterative tree traversal skills:

• Level-order traversal (collect nodes per level into separate lists)
• Find the maximum node in a binary tree (replace sum with max tracking)
• Count the leaves of a binary tree (increment counter only for leaf nodes)
• Iterative pre-order traversal (use a stack instead of a queue)

This problem and hundreds of others are available on Firecode, where over 50,000 engineers have practiced for technical interviews and landed roles at top companies. Consistent practice with problems like this builds the pattern recognition that makes interview day feel routine rather than stressful.

Solutions in Other Languages

Python

from collections import deque

class Solution:
    def sum_nodes(self, root):
        sum_total = 0
        if root is None:
            return sum_total

        queue = deque()
        queue.append(root)

        while queue:
            node = queue.popleft()
            sum_total += node.data
            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)

        return sum_total

JavaScript

class Solution {
  sumNodes(root) {
    let sum = 0;
    if (root === null) return sum;

    const queue = new Queue();
    queue.enqueue(root);

    while (queue.nonEmpty()) {
      const node = queue.dequeue();
      sum += node.data;
      if (node.left !== null) queue.enqueue(node.left);
      if (node.right !== null) queue.enqueue(node.right);
    }

    return sum;
  }
}

TypeScript

class Solution {
  sumNodes(root: TreeNode | null): number {
    let sum = 0;
    if (root === null) return sum;

    const queue: TreeNode[] = [];
    queue.push(root);

    while (queue.length > 0) {
      const node = queue.shift()!;
      sum += node.data;
      if (node.left !== null) queue.push(node.left);
      if (node.right !== null) queue.push(node.right);
    }

    return sum;
  }
}

C++

#include <queue>

class Solution {
public:
  int sumNodes(TreeNode *root) {
    int sum = 0;
    if (root == nullptr) return sum;

    std::queue<TreeNode *> queue;
    queue.push(root);

    while (!queue.empty()) {
      TreeNode *node = queue.front();
      queue.pop();
      sum += node->data;
      if (node->left != nullptr) queue.push(node->left);
      if (node->right != nullptr) queue.push(node->right);
    }

    return sum;
  }
};

Scala

import scala.collection.mutable

class Solution {
  def sumNodes(root: TreeNode): Int = {
    var sum = 0
    if (root == null) return sum

    val queue = mutable.Queue[TreeNode]()
    queue.enqueue(root)

    while (queue.nonEmpty) {
      val node = queue.dequeue()
      sum += node.data
      if (node.left != null) queue.enqueue(node.left)
      if (node.right != null) queue.enqueue(node.right)
    }

    sum
  }
}

Kotlin

import java.util.LinkedList

class Solution {
    fun sumNodes(root: TreeNode?): Int {
        var sum = 0
        if (root == null) return sum

        val queue = LinkedList<TreeNode?>()
        queue.offer(root)

        while (queue.isNotEmpty()) {
            val node = queue.poll()
            sum += node?.data ?: 0
            if (node?.left != null) queue.offer(node.left)
            if (node?.right != null) queue.offer(node.right)
        }

        return sum
    }
}

Ruby

class Solution
  def sum_nodes(root)
    sum = 0
    return sum if root.nil?

    queue = [root]

    until queue.empty?
      node = queue.shift
      sum += node.data
      queue.push(node.left) unless node.left.nil?
      queue.push(node.right) unless node.right.nil?
    end

    sum
  end
end

Rust

use std::collections::VecDeque;

impl Solution {
    pub fn sum_nodes(&self, root: Option<Box<TreeNode>>) -> i32 {
        let mut sum = 0;
        if root.is_none() {
            return sum;
        }

        let mut queue: VecDeque<Box<TreeNode>> = VecDeque::new();
        queue.push_back(root.unwrap());

        while let Some(node) = queue.pop_front() {
            sum += node.data;
            if let Some(left) = node.left {
                queue.push_back(left);
            }
            if let Some(right) = node.right {
                queue.push_back(right);
            }
        }

        sum
    }
}

Swift

class Solution {
    func sumNodes(_ root: TreeNode?) -> Int {
        var sum = 0
        if root == nil { return sum }

        var queue: [TreeNode] = [root!]

        while !queue.isEmpty {
            let node = queue.removeFirst()
            sum += node.data
            if let left = node.left { queue.append(left) }
            if let right = node.right { queue.append(right) }
        }

        return sum
    }
}

Dart

import 'dart:collection';

class Solution {
  int sumNodes(TreeNode? root) {
    int sum = 0;
    if (root == null) return sum;

    Queue<TreeNode> queue = Queue();
    queue.add(root);

    while (queue.isNotEmpty) {
      TreeNode node = queue.removeFirst();
      sum += node.data;
      if (node.left != null) queue.add(node.left!);
      if (node.right != null) queue.add(node.right!);
    }

    return sum;
  }
}

C#

public class Solution {
    public int sumNodes(TreeNode? root) {
        int sum = 0;
        if (root == null) return sum;

        var queue = new Queue<TreeNode>();
        queue.Enqueue(root);

        while (queue.Count > 0) {
            var node = queue.Dequeue();
            sum += node.data;
            if (node.left != null) queue.Enqueue(node.left);
            if (node.right != null) queue.Enqueue(node.right);
        }

        return sum;
    }
}

PHP

class Solution {
    public function sumNodes(?TreeNode $root): int {
        $sum = 0;
        if ($root === null) return $sum;

        $queue = new SplQueue();
        $queue->enqueue($root);

        while (!$queue->isEmpty()) {
            $node = $queue->dequeue();
            $sum += $node->data;
            if ($node->left !== null) $queue->enqueue($node->left);
            if ($node->right !== null) $queue->enqueue($node->right);
        }

        return $sum;
    }
}