Iteratively find the maximum node of a binary tree

You're warming up for a technical phone screen with Oracle when the interviewer asks you to find the largest value in a binary tree. Sounds simple enough, but then they add a constraint: "Do it iteratively, no recursion allowed." This twist forces you to think about tree traversal differently, trading the elegance of recursion for the explicit control of a queue-based approach. The problem is also sometimes known as "Find Maximum Value in Binary Tree" on other platforms, and it tests your ability to traverse a tree structure without leaning on the call stack.

TL;DR

Use breadth-first search with a queue to visit every node in the tree. Track the maximum value seen so far, starting from Integer.MIN_VALUE. For each node polled from the queue, compare its value against the running max and enqueue its children. When the queue empties, you have the answer. This runs in O(n) time and O(n) space.

Why This Problem Matters

Finding the maximum value in a binary tree is a building block for harder problems like finding the second largest node, validating BST properties, or computing level-order statistics. More importantly, the iterative constraint forces you to practice explicit queue and stack management, a skill that comes up repeatedly in interviews when interviewers want to see you work without recursion.

Binary Trees and Traversal: A Quick Refresher

A binary tree is a hierarchical structure where each node has at most two children. Unlike a binary search tree, a general binary tree has no ordering guarantee, so the maximum value could be hiding anywhere.

In this small tree, the root holds 4, the left child holds 6, and the right child holds 5. The maximum is 6, sitting in the left subtree. You cannot make any assumptions about where the largest value lives.

There are two families of traversal:

• Breadth-first (BFS): Visit nodes level by level using a queue
• Depth-first (DFS): Visit nodes branch by branch using a stack or recursion

Since the problem asks for an iterative solution, BFS with a queue is the most natural fit.

Understanding the Problem

Given: The root TreeNode of a binary tree Return: The maximum data value in the tree Constraints: The tree has 1 to 1000 nodes. Use an iterative approach, not recursion.

Here is a more complex example:

The tree 2 2 8 # # 5 10 has nodes with values 2, 2, 8, 5, and 10. The answer is 10, located in the bottom-right of the tree.

Edge Cases

1. Single node: Return that node's value
2. All negative values: The algorithm must handle negative numbers correctly
3. Skewed tree: All nodes on one side, effectively a linked list
4. Duplicate values: Multiple nodes share the maximum value

Consider this tree with negative values:

The root is -4, but the maximum is 10. Initializing max to 0 would incorrectly return 0 for a tree of all-negative values, so we initialize to Integer.MIN_VALUE.

Solution Approach

The strategy is straightforward. Visit every single node, keep track of the largest value you have seen, and return it when you are done.

BFS gives us a clean way to do this iteratively:

1. Create a queue and add the root
2. Initialize max to Integer.MIN_VALUE
3. While the queue is not empty, poll a node
4. If the node is not null, update max and enqueue its children
5. Return max

Let's trace through the example tree 2 2 8 # # 5 10:

The annotations show how max updates as BFS processes each node. It starts at negative infinity, jumps to 2 at the root, stays at 2 when visiting the left child, jumps to 8, stays at 8 for node 5, and finally reaches 10.

Here is the queue state at each step:

Implementation

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

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

public class Solution {
  public int maxData(TreeNode root) {
    // Create a queue for breadth-first traversal
    Deque<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    // Initialize max to the smallest possible integer
    int max = Integer.MIN_VALUE;

    // Process nodes until the queue is empty
    while (!queue.isEmpty()) {
      TreeNode node = queue.poll();
      if (node != null) {
        // Update max if this node's value is larger
        max = Math.max(node.data, max);

        // Enqueue both children for processing
        queue.offer(node.left);
        queue.offer(node.right);
      }
    }

    return max;
  }
}

A few things to note about this implementation:

• We use Deque (backed by LinkedList) as our queue. offer() adds to the tail, poll() removes from the head, giving us FIFO behavior.
• Null children are enqueued but filtered out on the next iteration. This keeps the code clean, avoiding separate null checks before each offer().
• Math.max(node.data, max) handles the comparison in a single readable line.

Why not DFS with a stack?

You absolutely could replace the queue with a stack. The only difference is traversal order: DFS explores depth-first while BFS goes level by level. Since we are visiting every node regardless, the final answer is identical. BFS is slightly easier to reason about because the queue processes nodes in the order you would draw them on a whiteboard.

Complexity Analysis

Time Complexity: O(n)

Every node is enqueued once and dequeued once. The work per node is O(1) - one comparison and up to two enqueue operations. Total: O(n).

Space Complexity: O(n)

The queue holds at most one full level of the tree at a time. For a complete binary tree, the last level contains roughly n/2 nodes. In a skewed tree (essentially a linked list), the queue holds just one node at a time. Worst case is O(n).

Common Pitfalls

1. Initializing max to 0: Fails for trees with all negative values. Always use Integer.MIN_VALUE (or the root's value).

2. Forgetting the null check: If you enqueue null children (as our solution does), you must check for null when polling. Otherwise you get a NullPointerException.

3. Using recursion: The problem explicitly asks for an iterative solution. In an interview, ignoring constraints signals that you are not reading carefully.

4. Confusing this with BST max: In a BST, you would just follow right children. A general binary tree requires visiting every node.

Handling a Skewed Tree

A skewed tree is the worst case for depth but actually the best case for queue space:

The queue never holds more than two nodes (the current node's children), so space usage is O(1) for this shape. The time is still O(n) since every node must be visited.

Interview Tips

1. Clarify the tree type: Ask whether it is a BST or a general binary tree. For a BST, you can find the max in O(h) time by following right children.

2. State your approach upfront: "I'll use BFS with a queue to visit every node and track the running maximum."

3. Mention the recursive alternative: Even though the problem forbids it, saying "this could also be solved recursively with max(root.data, max(left, right))" shows depth of understanding.

4. Walk through an example: Trace through a small tree (3-4 nodes) showing the queue state at each step, exactly like the state evolution diagram above.

5. Discuss tradeoffs: BFS uses O(w) space where w is the maximum width. DFS uses O(h) space where h is the height. For balanced trees, BFS uses more space. For skewed trees, DFS uses more space.

Key Takeaways

• In a general binary tree, finding the max requires visiting every node because there is no ordering guarantee. This is fundamentally different from a BST.
• BFS with a queue is the most natural iterative traversal. The pattern of poll, process, enqueue children applies to dozens of tree problems.
• Always initialize your tracking variable to Integer.MIN_VALUE (or the language equivalent) when searching for a maximum. Using 0 or the root value can cause subtle bugs.
• The iterative BFS pattern here transfers directly to problems like level-order traversal, finding the minimum depth, and checking tree symmetry.
• Time is O(n), space is O(n) worst case. Neither can be improved since every node must be visited.

Practice Makes Perfect

Once you are comfortable with this iterative max-finding approach, try these related problems to build on the same BFS pattern:

• Find the size of a binary tree (count all nodes iteratively)
• Iteratively find a node in a binary tree (search instead of max)
• Minimum depth of a binary tree (level-order traversal with early exit)
• Level-order traversal (return nodes grouped by level)

This problem and thousands of others are available on Firecode, where over 50,000 users have prepared for technical interviews and landed roles at top tech companies. Whether you are just starting your interview prep or polishing your tree traversal skills, consistent practice on fundamentals like this will pay off.

Solutions in Other Languages

Python

import sys
from collections import deque


class Solution:
    def max_data(self, root):
        queue = deque()
        queue.append(root)
        max_data = -sys.maxsize - 1

        while len(queue) > 0:
            node = queue.popleft()
            if node is not None:
                max_data = max(max_data, node.data)
                queue.append(node.left)
                queue.append(node.right)

        return max_data

JavaScript

class Solution {
  maxData(root) {
    const queue = new Queue();
    queue.enqueue(root);
    let max = Number.NEGATIVE_INFINITY;

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

    return max;
  }
}

TypeScript

class Solution {
  maxData(root: TreeNode): number {
    const queue = new Queue<TreeNode | null>();
    queue.offer(root);
    let max = Number.NEGATIVE_INFINITY;

    while (!queue.isEmpty()) {
      const node = queue.poll();
      if (node !== null) {
        max = Math.max(node.data, max);
        queue.offer(node.left);
        queue.offer(node.right);
      }
    }

    return max;
  }
}

C++

#include <queue>

class Solution {
public:
  int maxData(TreeNode *root) {
    std::queue<TreeNode *> queue;
    queue.push(root);
    int max = INT_MIN;

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

    return max;
  }
};

Go

func (s *Solution) MaxData(root *TreeNode) int {
    queue := NewQueue()
    queue.Offer(root)
    max := math.MinInt

    for !queue.IsEmpty() {
        node := queue.Poll().(*TreeNode)
        if node != nil {
            if node.Data > max {
                max = node.Data
            }
            queue.Offer(node.Left)
            queue.Offer(node.Right)
        }
    }

    return max
}

Scala

import scala.collection.mutable

class Solution {
  def maxData(root: TreeNode): Int = {
    val queue = new mutable.Queue[TreeNode]
    queue.enqueue(root)
    var max = Int.MinValue

    while (queue.nonEmpty) {
      val node = queue.dequeue()
      if (node != null) {
        max = Math.max(node.data, max)
        queue.enqueue(node.left)
        queue.enqueue(node.right)
      }
    }

    max
  }
}

Kotlin

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

class Solution {
    fun maxData(root: TreeNode?): Int {
        val queue: Deque<TreeNode?> = LinkedList()
        queue.offer(root)
        var max = Int.MIN_VALUE

        while (queue.isNotEmpty()) {
            val node = queue.poll()
            if (node != null) {
                max = maxOf(node.data, max)
                queue.offer(node.left)
                queue.offer(node.right)
            }
        }

        return max
    }
}

Ruby

class Solution
  def max_data(root)
    queue = [root]
    max = -Float::INFINITY

    while !queue.empty?
      node = queue.shift
      unless node.nil?
        max = [node.data, max].max
        queue.push(node.left)
        queue.push(node.right)
      end
    end

    max
  end
end

Rust

pub fn max_data(&self, root: Option<Box<TreeNode>>) -> i32 {
    let mut queue: VecDeque<Option<Box<TreeNode>>> = VecDeque::new();
    queue.push_back(root);
    let mut max_value = i32::MIN;

    while let Some(node_opt) = queue.pop_front() {
        if let Some(node) = node_opt {
            max_value = max_value.max(node.data);
            queue.push_back(node.left);
            queue.push_back(node.right);
        }
    }

    max_value
}

Swift

func maxData(_ root: TreeNode?) -> Int {
    var queue: [TreeNode?] = []
    queue.append(root)
    var maxValue = Int.min

    while !queue.isEmpty {
        let node = queue.removeFirst()
        if node != nil {
            maxValue = max(node!.data, maxValue)
            queue.append(node!.left)
            queue.append(node!.right)
        }
    }

    return maxValue
}

Dart

int maxData(TreeNode? root) {
    Queue<TreeNode> queue = Queue();
    queue.add(root!);
    int maxVal = -(1 << 31);

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

    return maxVal;
}

PHP

public function maxData(TreeNode $root): int {
    $queue = [$root];
    $max = PHP_INT_MIN;

    while (!empty($queue)) {
        $node = array_shift($queue);
        if ($node !== null) {
            $max = max($node->data, $max);
            $queue[] = $node->left;
            $queue[] = $node->right;
        }
    }

    return $max;
}

C#

public int maxData(TreeNode? root) {
    var queue = new Queue<TreeNode?>();
    queue.Enqueue(root);
    var max = int.MinValue;

    while (queue.Count > 0) {
        var node = queue.Dequeue();
        if (node != null) {
            max = Math.Max(node.data, max);
            queue.Enqueue(node.left);
            queue.Enqueue(node.right);
        }
    }

    return max;
}