Sum all nodes of a binary tree

You're working through a technical screen and the interviewer pulls up a binary tree on the shared editor. "Let's start with something warm-up level," they say. "Given this tree, can you sum all the node values?" It sounds almost too simple, but this problem is a perfect litmus test for recursive thinking. If you can articulate the base case, the recursive decomposition, and why it works, you've demonstrated the exact skill set that harder tree problems build on. This problem is also known as "Sum of All Nodes in Binary Tree" on other platforms.

TL;DR

To sum all nodes in a binary tree, use the recursive formula root.data + sumNodes(root.left) + sumNodes(root.right) with a base case that returns 0 for null nodes. This visits every node exactly once for O(n) time and uses O(h) stack space where h is the tree height. For a balanced tree, that is O(log n); for a skewed tree, O(n).

Why This Problem Matters

Summing all nodes in a binary tree is one of the cleanest introductions to recursive tree accumulation. The pattern you learn here, base case on null, combine current node with recursive results from children, is the exact same skeleton used for finding tree height, counting nodes, checking balance, and computing diameter. Companies use it as a warm-up question because it reveals whether you truly understand recursion or just memorize solutions.

Binary Trees: A Quick Refresher

A binary tree is a hierarchical structure where each node has at most two children. Here is a simple example:

Each node stores a data value along with pointers to its left and right children. Leaf nodes have both children set to null. The tree above has five nodes with values 5, 3, 8, 1, and 4, and their sum is 21.

Understanding the Problem

Given the root TreeNode of a binary tree, return the sum of all node data values.

Here is the example from the problem statement:

The tree 1 2 3 # # 4 5 contains nodes with values 1, 2, 3, 4, and 5. The expected result is 1 + 2 + 3 + 4 + 5 = 15.

Constraints:

• The tree will contain a maximum of 100 nodes.
• An empty tree sums to 0.

Edge Cases

1. Empty tree (null root): return 0
2. Single node: return that node's data value
3. Skewed tree (all nodes on one side): recursion still works, but the call stack grows to O(n)

A skewed tree like this is really just a linked list in disguise. The algorithm handles it fine, but the stack depth matches the number of nodes.

Solution Approach

Think about what happens when you stand at any node in the tree. To compute the total sum from that node downward, you need three things:

1. The current node's own data value
2. The sum of everything in the left subtree
3. The sum of everything in the right subtree

Add those three together and you have your answer. The left and right subtree sums are smaller instances of the same problem, which is exactly what recursion is built for.

Recursive Decomposition

Let's trace through the example tree to see this in action:

Starting at node 1:

• Ask the left subtree (rooted at 2) for its sum. Node 2 is a leaf, so its sum is just 2.
• Ask the right subtree (rooted at 3) for its sum. Node 3 has children 4 and 5, so its subtree sum is 3 + 4 + 5 = 12.
• Combine: 1 + 2 + 12 = 15.

The recursion bottoms out whenever it hits a null child, returning 0. That zero propagates back up without contributing anything to the total, which is exactly right.

Implementation

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

public class Solution {
  public int sumNodes(TreeNode root) {
    // Base case: an empty subtree contributes nothing
    if (root == null) return 0;

    // Current node's data + sum of left subtree + sum of right subtree
    return root.data + sumNodes(root.left) + sumNodes(root.right);
  }
}

That is the entire solution. Two lines of logic. The elegance here is not accidental; it reflects the recursive structure of the tree itself.

Tracing the Recursion

Watch how the recursive calls unfold on our example tree. Use the controls to step through at your own pace:

Each leaf returns its own value (since both children are null and contribute 0). Internal nodes combine their value with what bubbles up from below. The final answer, 15, appears when the root call finishes.

Complexity Analysis

Time Complexity: O(n)

Every node is visited exactly once. At each node we do O(1) work: a null check, an addition, and two recursive calls. With n nodes total, the running time is O(n).

Space Complexity: O(h)

The space comes from the recursive call stack. At any point during execution, the stack holds frames for every ancestor of the current node, which is at most the height h of the tree.

• Balanced tree: h = O(log n), so space is O(log n)
• Skewed tree: h = n, so space is O(n)

The problem statement lists O(n) as the space complexity because it accounts for the worst case.

Could We Do Better on Space?

An iterative approach using a queue (level-order traversal) would use O(w) space where w is the maximum width of the tree. For a balanced tree, the widest level has roughly n/2 nodes, so the iterative approach does not actually save space in that case. For interviews, the recursive solution is the standard answer.

Common Pitfalls

1. Forgetting the base case. Without the null check, the first call on a leaf's child throws a NullPointerException. Always handle null before accessing root.data.

2. Returning the wrong value for null. Some candidates return -1 or Integer.MIN_VALUE for null nodes. The correct return is 0, because an empty subtree should contribute nothing to the sum.

3. Trying to iterate without a data structure. Unlike arrays, you cannot iterate over a tree with a simple for loop. You either recurse or use an explicit stack/queue.

Interview Tips

When you get this problem in an interview:

1. Clarify the TreeNode structure. Confirm that each node has data, left, and right fields. Some implementations use val instead of data.

2. State your approach before coding. "I'll use recursion. The base case returns 0 for null. The recursive case adds the current node's data to the sum of its left and right subtrees."

3. Mention complexity proactively. "This runs in O(n) time since we visit every node, and O(h) space for the call stack."

4. Anticipate follow-ups. The interviewer might ask you to sum only leaf nodes, sum nodes at a specific depth, or find the maximum path sum. All of these build on the same recursive skeleton.

Key Takeaways

• The recursive formula root.data + sumNodes(root.left) + sumNodes(root.right) with base case 0 for null is the standard approach, and it generalizes to many tree accumulation problems.
• Time is O(n) because every node is visited once. Space is O(h) for the call stack, which ranges from O(log n) for balanced trees to O(n) for skewed trees.
• Always return 0 for a null node, not a sentinel value. An empty subtree should be invisible to the sum.
• This "combine current node with recursive subtree results" pattern is the foundation for tree height, node count, balance check, diameter, and path sum problems.
• In interviews, state your base case and recursive case before writing code. Clear articulation of the recursion is often worth more than the code itself.

Solutions in Other Languages

Python

class Solution:
    def sum_nodes(self, root: TreeNode) -> int:
        if root is None:
            return 0

        return root.data + self.sum_nodes(root.left) + self.sum_nodes(root.right)

JavaScript

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

    return root.data + this.sumNodes(root.left) + this.sumNodes(root.right);
  }
}

TypeScript

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

    return root.data + this.sumNodes(root.left) + this.sumNodes(root.right);
  }
}

C++

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

    return root->data + sumNodes(root->left) + sumNodes(root->right);
  }
};

Go

func (s *Solution) SumNodes(root *TreeNode) int {
    if root == nil {
        return 0
    }

    return root.Data + s.SumNodes(root.Left) + s.SumNodes(root.Right)
}

Scala

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

Kotlin

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

        return root.data + sumNodes(root.left) + sumNodes(root.right)
    }
}

Swift

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

        return root!.data + sumNodes(root!.left) + sumNodes(root!.right)
    }
}

Rust

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

        let node = root.unwrap();
        node.data + self.sum_nodes(node.left) + self.sum_nodes(node.right)
    }
}

Ruby

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

    root.data + sum_nodes(root.left) + sum_nodes(root.right)
  end
end

Dart

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

    return root.data + sumNodes(root.left) + sumNodes(root.right);
  }
}

PHP

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

        return $root->data + $this->sumNodes($root->left) + $this->sumNodes($root->right);
    }
}

C#

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

        return root.data + sumNodes(root.left) + sumNodes(root.right);
    }
}

Practice Makes Perfect

Once you have this recursive pattern down, try these related problems to solidify your understanding:

• Find the size of a binary tree (count nodes instead of summing them)
• Height of a binary tree (use max instead of +)
• Recursively find the maximum node of a binary tree

All three use the same base-case-plus-combine structure. The only thing that changes is the operation at each node.

Remember, consistent practice is the key to succeeding in coding interviews. This problem and thousands of others are available on Firecode, where over 50,000 users have successfully prepared for technical interviews and landed six and seven-figure jobs at top tech companies. Whether you're just starting or preparing for your dream job, mastering fundamentals like this will set you up for success.