Iteratively find a node in a binary tree

You're warming up for a phone screen and the interviewer asks a deceptively simple question: "Given a binary tree, can you check whether a specific value exists in it, without using recursion?" This problem, also known as "Search in a Binary Tree" on other platforms, is a staple in technical interviews because it tests two things at once: your understanding of tree traversal and your ability to convert recursive thinking into iterative code. It's a great opportunity to show you can work with queues and BFS, skills that transfer directly to harder problems like level-order traversal, shortest path algorithms, and serialization.

TL;DR

Use breadth-first search with a queue. Add the root to the queue, then loop: poll a node, check if its value matches the target, and enqueue its non-null children. If you find a match, return true. If the queue empties without a match, return false. This runs in O(n) time and O(n) space in the worst case. The key detail is handling the null root edge case before touching the queue.

Why This Problem Matters

Searching a binary tree iteratively is one of the first problems where you break free from the comfort of recursion. Many candidates can write a recursive tree search in seconds, but doing it iteratively forces you to understand the mechanics of tree traversal at a deeper level. You have to manage the traversal state yourself with a data structure, and that skill is the foundation for BFS-based problems that come up constantly in interviews.

Binary Trees and BFS: A Quick Refresher

A binary tree is a hierarchical structure where each node has at most two children. Unlike a binary search tree, there's no ordering guarantee, so we can't take shortcuts when searching. We have to potentially visit every single node.

Breadth-first search (BFS) visits nodes level by level. Starting from the root, it processes all nodes at depth 0, then depth 1, then depth 2, and so on. The secret ingredient is a queue: a first-in, first-out (FIFO) data structure that ensures we always process the oldest enqueued node next.

Think of it like a customer service line. The root gets in line first. When it's processed, its children join the back of the line. Each child, when it reaches the front, sends its own children to the back. The result is a neat, level-by-level sweep through the tree.

Understanding the Problem

Let's pin down the requirements:

Given: The root TreeNode of a binary tree and an integer n Find: Whether any node in the tree has a data value equal to n Return: true if found, false otherwise Constraint: Solve iteratively (no recursion)

Here's the example from the problem:

tree: 1 2 3 # # 4 5

    1
   / \
  2   3
     / \
    4   5

findNode(tree, 2) -> true
findNode(tree, 6) -> false

Edge Cases to Consider

1. Null root: The tree is empty, so no value can exist. Return false.
2. Single node: The root is the only node. Check its value and return.
3. Target at a leaf: BFS must reach the deepest level to find it.
4. Target not in tree: BFS exhausts the entire tree and returns false.
5. Negative values: Node values can be negative, so the comparison must handle all integers.

Solution Approach

Since we can't use recursion, we need a way to remember which nodes still need to be visited. That's where the queue comes in.

The BFS Strategy

The algorithm follows a simple loop:

1. Handle the null root edge case upfront
2. Create a queue and add the root
3. While the queue is not empty:
   • Poll the front node
   • If its value matches the target, return true
   • Otherwise, enqueue its non-null left and right children
4. If we exit the loop, the target was not found. Return false.

Let's visualize what happens when we search for the value 4 in our example tree:

The green path shows the route BFS takes to reach node 4. It processes level 0 (node 1), then level 1 (nodes 2 and 3), then level 2 where it finds node 4.

Queue State Evolution

Here's how the queue changes at each step of that search:

Each step polls the front of the queue, checks the value, and enqueues children. The process stops the moment we find our target.

What Happens When the Value Doesn't Exist?

When searching for a value like 6, BFS visits every node in the tree:

All paths are explored (highlighted in red). Every node is polled and checked, but none match. The queue eventually empties, and we return false.

Implementation

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

Here's the Java solution with a walkthrough:

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

public class Solution {
  public Boolean findNode(TreeNode root, int n) {
    // Handle the null root edge case
    if (root == null) return false;

    // Create a queue for breadth-first traversal
    Deque<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    // Process nodes level by level
    while (!queue.isEmpty()) {
      TreeNode node = queue.poll();

      // Check if this node's value matches the target
      if (node.data == n) return true;

      // Enqueue non-null children for future processing
      if (node.left != null) queue.offer(node.left);
      if (node.right != null) queue.offer(node.right);
    }

    // Target not found after traversing the entire tree
    return false;
  }
}

Let's trace through the execution with findNode(root, 4) on our example tree:

Iteration 1:

• Poll node 1 from the queue
• Is 1 == 4? No
• Enqueue left child (2) and right child (3)
• Queue: [2, 3]

Iteration 2:

• Poll node 2
• Is 2 == 4? No
• Node 2 has no children
• Queue: [3]

Iteration 3:

• Poll node 3
• Is 3 == 4? No
• Enqueue left child (4) and right child (5)
• Queue: [4, 5]

Iteration 4:

• Poll node 4
• Is 4 == 4? Yes! Return true

The algorithm found the target after processing just 4 nodes, without needing to visit node 5.

BFS Traversal Animation

Here's the full traversal animated step by step:

Complexity Analysis

Time Complexity: O(n)

In the worst case, the target value either doesn't exist or sits in the last node we visit. Every node gets polled from the queue exactly once, checked, and its children enqueued. That's constant work per node, so the total time is O(n) where n is the number of nodes.

In the best case, the root itself matches, giving O(1). But we always analyze worst-case complexity.

Space Complexity: O(n)

The queue holds nodes waiting to be processed. In the worst case, for a complete binary tree, the bottom level contains roughly n/2 nodes. All of them can sit in the queue simultaneously before any gets polled, giving O(n) space.

For a skewed tree (every node has only one child), the queue never holds more than one node at a time, so the space drops to O(1). But we report worst-case: O(n).

BFS vs. DFS Trade-offs

BFS uses more space on wide, balanced trees. DFS uses more space on deep, narrow trees. For a general "does this node exist?" question, both work equally well. The problem specifically asks for iterative practice, making BFS with a queue the natural fit.

Common Pitfalls

1. Forgetting the null root check: If you enqueue a null root, queue.poll() returns null and node.data throws a NullPointerException. Always check before creating the queue.

2. Enqueuing null children: Some implementations skip the null check and instead check for null after polling. Both work, but forgetting to handle nulls at either point causes crashes.

   // Approach A: Check before enqueuing (cleaner)
   if (node.left != null) queue.offer(node.left);
   
   // Approach B: Check after polling (also valid)
   TreeNode node = queue.poll();
   if (node == null) continue;
   

3. Using a stack instead of a queue: Swapping offer/poll (FIFO) for push/pop (LIFO) silently converts BFS into DFS. The search still works, but the traversal order changes. If the interviewer specifically asks for BFS, a stack is incorrect.

4. Returning true outside the loop: The default return value must be false, since reaching that line means no match was found.

Interview Tips

When solving this problem in an interview:

1. Clarify the tree type: "Is this a general binary tree or a BST?" This matters because BST search is O(log n) while general tree search is O(n).

2. State your approach upfront: "I'll use BFS with a queue to visit every node iteratively, checking each one against the target."

3. Draw the queue state: Sketch how the queue evolves over 2-3 iterations. This shows the interviewer you understand BFS mechanics, not just the code pattern.

4. Mention the DFS alternative: "I could also use a stack for iterative DFS. Same time complexity, but different space characteristics depending on tree shape."

5. Handle edge cases explicitly: Start your code with the null check and mention why. Interviewers notice when you think defensively.

Key Takeaways

• BFS uses a queue to traverse a binary tree level by level, checking each node against the target. If the queue empties, the value does not exist.
• Always guard against a null root before enqueueing. This is the most common source of runtime errors in tree traversal code.
• Time complexity is O(n) because every node may need to be visited. Space is O(n) in the worst case due to the queue holding an entire tree level.
• Swapping the queue for a stack converts BFS into iterative DFS. Both find the node, but the traversal order and space characteristics differ.
• This problem is a building block for harder BFS problems: level-order traversal, zigzag traversal, shortest path in unweighted graphs, and tree serialization all build on the same queue-based loop.

Practice Makes Perfect

Once you're comfortable with iterative tree search, try these related problems to deepen your BFS and tree traversal skills:

• Find the height of a binary tree (iteratively with BFS)
• Level-order traversal of a binary tree
• Find the size of a binary tree
• Check if a binary tree is symmetric

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 iterative tree traversal will set you up for success.

Solutions in Other Languages

Python

from collections import deque

class Solution:
    def find_node(self, root, n):
        queue = deque()
        queue.append(root)
        while queue:
            node = queue.popleft()
            if node is not None:
                if node.data == n:
                    return True
                queue.append(node.left)
                queue.append(node.right)
        return False

JavaScript

class Solution {
  findNode(root, n) {
    const queue = new Queue();
    queue.enqueue(root);
    while (queue.nonEmpty()) {
      const node = queue.dequeue();
      if (node !== null) {
        if (node.data === n) return true;
        queue.enqueue(node.left).enqueue(node.right);
      }
    }
    return false;
  }
}

TypeScript

class Solution {
  findNode(root: TreeNode | null, n: number): boolean {
    if (root === null) return false;
    const queue: TreeNode[] = [];
    queue.push(root);
    while (queue.length > 0) {
      const node = queue.shift()!;
      if (node.data === n) return true;
      if (node.left !== null) queue.push(node.left);
      if (node.right !== null) queue.push(node.right);
    }
    return false;
  }
}

C++

#include <queue>

class Solution {
public:
  bool findNode(TreeNode *root, int n) {
    std::queue<TreeNode *> queue;
    queue.push(root);
    while (!queue.empty()) {
      TreeNode *node = queue.front();
      queue.pop();
      if (node != nullptr) {
        if (node->data == n) return true;
        queue.push(node->left);
        queue.push(node->right);
      }
    }
    return false;
  }
};

Go

func (s *Solution) FindNode(root *TreeNode, n int) bool {
    queue := NewQueue()
    queue.Offer(root)
    for !queue.IsEmpty() {
        node := queue.Poll().(*TreeNode)
        if node != nil {
            if node.Data == n {
                return true
            }
            queue.Offer(node.Left)
            queue.Offer(node.Right)
        }
    }
    return false
}

Scala

import scala.collection.mutable

class Solution {
  def findNode(root: TreeNode, n: Int): Boolean = {
    val queue = new mutable.Queue[TreeNode]
    queue.enqueue(root)
    while (queue.nonEmpty) {
      val node = queue.dequeue()
      if (node != null) {
        if (node.data == n) return true
        queue.enqueue(node.left).enqueue(node.right)
      }
    }
    false
  }
}

Kotlin

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

class Solution {
    fun findNode(root: TreeNode?, n: Int): Boolean {
        if (root == null) return false
        val queue: Deque<TreeNode> = LinkedList()
        queue.offer(root)
        while (!queue.isEmpty()) {
            val node = queue.poll()
            if (node.data == n) return true
            if (node.left != null) queue.offer(node.left)
            if (node.right != null) queue.offer(node.right)
        }
        return false
    }
}

Swift

class Solution {
    func findNode(_ root: TreeNode?, _ n: Int) -> Bool {
        if root == nil { return false }
        var queue: [TreeNode] = [root!]
        while !queue.isEmpty {
            let node = queue.removeFirst()
            if node.data == n { return true }
            if let left = node.left { queue.append(left) }
            if let right = node.right { queue.append(right) }
        }
        return false
    }
}

Rust

use std::collections::VecDeque;

impl Solution {
    pub fn find_node(&self, root: Option<Box<TreeNode>>, n: i32) -> bool {
        if root.is_none() { return false; }
        let mut queue: VecDeque<Box<TreeNode>> = VecDeque::new();
        queue.push_back(root.unwrap());
        while let Some(node) = queue.pop_front() {
            if node.data == n { return true; }
            if let Some(left) = node.left { queue.push_back(left); }
            if let Some(right) = node.right { queue.push_back(right); }
        }
        false
    }
}

Ruby

class Solution
  def find_node(root, n)
    queue = []
    queue.push(root)
    while !queue.empty?
      node = queue.shift
      unless node.nil?
        return true if node.data == n
        queue.push(node.left)
        queue.push(node.right)
      end
    end
    false
  end
end

Dart

import 'dart:collection';

class Solution {
  bool findNode(TreeNode? root, int n) {
    if (root == null) return false;
    Queue<TreeNode> queue = Queue();
    queue.add(root);
    while (queue.isNotEmpty) {
      TreeNode node = queue.removeFirst();
      if (node.data == n) return true;
      if (node.left != null) queue.add(node.left!);
      if (node.right != null) queue.add(node.right!);
    }
    return false;
  }
}

C#

public class Solution {
    public bool findNode(TreeNode? root, int n) {
        if (root == null) return false;
        var queue = new Queue<TreeNode>();
        queue.Enqueue(root);
        while (queue.Count > 0) {
            var node = queue.Dequeue();
            if (node.data == n) return true;
            if (node.left != null) queue.Enqueue(node.left);
            if (node.right != null) queue.Enqueue(node.right);
        }
        return false;
    }
}

PHP

class Solution {
    public function findNode(?TreeNode $root, int $n): bool {
        if ($root === null) return false;
        $queue = [$root];
        while (!empty($queue)) {
            $node = array_shift($queue);
            if ($node->data === $n) return true;
            if ($node->left !== null) $queue[] = $node->left;
            if ($node->right !== null) $queue[] = $node->right;
        }
        return false;
    }
}