The deepest node of a binary tree

You're midway through a technical screen at Adobe when the interviewer draws a tree on the shared editor and asks, "How would you find the value of the deepest node?" It sounds straightforward, but there's a twist: if two nodes sit at the same depth, you need the rightmost one. This problem, sometimes known as "Find Deepest Node in Binary Tree" on other platforms, tests your command of breadth-first traversal and queue-based algorithms. Companies like Adobe and Visa use it to gauge how fluently you work with tree data structures.

TL;DR

Use BFS (level-order traversal) with a queue. Enqueue the root, then repeatedly dequeue a node and enqueue its children (left first, then right). When the queue empties, the last dequeued node is the rightmost node at the deepest level. This runs in O(n) time and O(n) space. The trick is that processing left before right at every level means the final node processed is always the rightmost at the bottom.

Why This Problem Matters

Finding the deepest node is a clean entry point into BFS on trees. Once you have this pattern down, problems like level-order traversal, right-side view of a binary tree, and zigzag order become variations on the same theme. It also reinforces how queue ordering (FIFO) naturally produces level-by-level processing, a concept that transfers directly to graph BFS.

Binary Trees and Level-Order Traversal

A binary tree is a hierarchical structure where each node has at most two children. When we need to process nodes level by level, we reach for BFS rather than DFS. The queue guarantees that all nodes at depth d are processed before any node at depth d+1.

In the tree above, the root is 1, level 1 has nodes 2 and 3, and level 2 has nodes 4 and 5. The deepest level is level 2, and the rightmost node there is 5. That is our answer.

Understanding the Problem

Given: The root TreeNode of a binary tree. Find: The data value of the deepest node. If multiple nodes share the deepest level, return the rightmost one. Constraints: The tree has between 1 and 1000 nodes. Aim for linear time and space.

Here is the example from the problem:

The highlighted path leads to node 5. Both 4 and 5 live at depth 2, but since 5 is the rightmost, that is the answer.

Edge Cases

1. Single node: The root is the deepest node.

2. Skewed tree (all nodes on one side): The leaf at the end of the chain is the deepest.

3. Complete tree: Every level is full; the rightmost node on the last level wins.

Solution Approach

Think about how a queue processes items: first in, first out. If we enqueue a node's left child before its right child, then within any given level the rightmost node will be the last one dequeued at that level. Across the entire tree, the very last node dequeued is the rightmost node at the deepest level.

That single observation is the whole algorithm:

1. Start a queue with the root.
2. Dequeue a node, enqueue its children (left then right).
3. Repeat until the queue is empty.
4. The last dequeued node holds the answer.

No depth tracking, no comparisons. The FIFO ordering handles everything.

Tracing Through the Example

Let's walk through the BFS on our example tree (1 2 3 # # 4 5):

After every node has been dequeued, currentNode points to 5, the rightmost node at the deepest level. We return currentNode.data.

Implementation

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

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

public class Solution {
  public int deepestNode(TreeNode root) {
    // Create a queue and seed it with the root
    Deque<TreeNode> queue = new LinkedList<>();
    TreeNode currentNode = root;
    queue.offer(currentNode);

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

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

    // After the loop, currentNode is the last node dequeued:
    // the rightmost node at the deepest level.
    return currentNode.data;
  }
}

Let's trace through a larger tree to cement the idea:

For the tree 1 2 3 # # 4 5 6 # 8 # 9 # # # 11 # 12, BFS visits levels 0 through 4. The last two nodes dequeued are 11 and then 12. Since 12 is dequeued last (it is rightmost at depth 4), the method returns 12.

Complexity Analysis

Time Complexity: O(n)

Every node is enqueued and dequeued exactly once. Each of those operations takes O(1) with a linked-list-backed queue. Total work is proportional to the number of nodes.

Space Complexity: O(n)

The queue's maximum size depends on the tree's width. In a complete binary tree, the bottom level holds roughly n/2 nodes, so the worst-case space is O(n). For a skewed tree the queue never holds more than one node, giving O(1) in the best case. Since we need to account for the worst case, we say O(n).

Common Pitfalls

1. Enqueueing right before left. The algorithm still finds the deepest level, but the last dequeued node would be the leftmost instead of the rightmost. Always enqueue left first if the problem asks for the rightmost.

2. Using a stack instead of a queue. A stack gives you DFS, not BFS. The last node popped from a stack is not guaranteed to be at the deepest level.

3. Forgetting to check for null children. Enqueuing a null child leads to a NullPointerException on the next iteration.

4. Overcomplicating with depth tracking. Some candidates maintain a maxDepth variable and compare at every step. That works, but it is unnecessary overhead. Let the queue do the work.

Interview Tips

When you see this problem in an interview:

1. Clarify the tiebreaker. Ask whether "deepest" means the rightmost at the maximum level or any node at the maximum level. This shows attention to detail.

2. State your approach upfront. "I will use BFS with a queue. By enqueuing left before right, the last node dequeued is the rightmost at the deepest level."

3. Mention the alternative. "DFS can also work by tracking depth, but BFS is a more natural fit here because the answer falls out directly from the traversal order."

4. Be ready for follow-ups. Common extensions include returning all nodes at the deepest level, finding the left-side view, or computing the width of each level.

Key Takeaways

• BFS with a queue is the textbook approach for level-order tree problems. The FIFO ordering naturally groups nodes by depth.
• Enqueuing left before right ensures that within each level, the rightmost node is dequeued last. The very last node dequeued across the entire traversal is the deepest rightmost node.
• Time is O(n) and space is O(n). No depth counters or auxiliary maps are needed.
• This pattern extends directly to right-side view, level-order grouping, and zigzag traversal problems.
• Always check for null children before enqueuing to avoid null pointer errors during interviews.

Related Problems and Practice

Once this clicks, try these related tree BFS problems to reinforce the pattern:

• Level-order traversal (group nodes by level)
• Right-side view of a binary tree
• Zigzag level-order traversal
• Minimum depth of a binary tree

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

Solutions in Other Languages

Python

from collections import deque

class Solution:
    def deepest_node(self, root):
        queue = deque()
        current_node = root
        queue.append(current_node)

        while len(queue) > 0:
            current_node = queue.popleft()
            if current_node.left is not None:
                queue.append(current_node.left)
            if current_node.right is not None:
                queue.append(current_node.right)

        return current_node.data

JavaScript

class Solution {
  deepestNode(root) {
    const queue = [];
    let currentNode = root;
    queue.push(currentNode);

    while (queue.length > 0) {
      currentNode = queue.shift();
      if (currentNode.left !== null) queue.push(currentNode.left);
      if (currentNode.right !== null) queue.push(currentNode.right);
    }

    return currentNode.data;
  }
}

TypeScript

class Solution {
  deepestNode(root: TreeNode): number {
    const queue: TreeNode[] = [];
    let currentNode: TreeNode = root;
    queue.push(currentNode);

    while (queue.length > 0) {
      currentNode = queue.shift()!;
      if (currentNode.left !== null) queue.push(currentNode.left);
      if (currentNode.right !== null) queue.push(currentNode.right);
    }

    return currentNode.data;
  }
}

C++

#include <queue>

class Solution {
public:
  int deepestNode(TreeNode *root) {
    std::queue<TreeNode *> queue;
    TreeNode *currentNode = root;
    queue.push(currentNode);

    while (!queue.empty()) {
      currentNode = queue.front();
      queue.pop();
      if (currentNode->left != nullptr) queue.push(currentNode->left);
      if (currentNode->right != nullptr) queue.push(currentNode->right);
    }

    return currentNode->data;
  }
};

Go

func DeepestNode(root *TreeNode) int {
    queue := []*TreeNode{root}
    var currentNode *TreeNode

    for len(queue) > 0 {
        currentNode = queue[0]
        queue = queue[1:]
        if currentNode.Left != nil {
            queue = append(queue, currentNode.Left)
        }
        if currentNode.Right != nil {
            queue = append(queue, currentNode.Right)
        }
    }

    return currentNode.Data
}

Scala

import scala.collection.mutable

class Solution {
  def deepestNode(root: TreeNode): Int = {
    val queue = mutable.Queue[TreeNode]()
    var currentNode = root
    queue.enqueue(currentNode)

    while (queue.nonEmpty) {
      currentNode = queue.dequeue()
      if (currentNode.left != null) queue.enqueue(currentNode.left)
      if (currentNode.right != null) queue.enqueue(currentNode.right)
    }

    currentNode.data
  }
}

Kotlin

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

class Solution {
    fun deepestNode(root: TreeNode): Int {
        val queue: Deque<TreeNode> = LinkedList()
        var currentNode: TreeNode = root
        queue.offer(currentNode)

        while (queue.isNotEmpty()) {
            currentNode = queue.poll()
            if (currentNode.left != null) queue.offer(currentNode.left)
            if (currentNode.right != null) queue.offer(currentNode.right)
        }

        return currentNode.data
    }
}

Ruby

class Solution
  def deepest_node(root)
    queue = [root]
    current_node = root

    until queue.empty?
      current_node = queue.shift
      queue.push(current_node.left) unless current_node.left.nil?
      queue.push(current_node.right) unless current_node.right.nil?
    end

    current_node.data
  end
end

Rust

use std::collections::VecDeque;

impl Solution {
    pub fn deepest_node(&self, root: Option<Box<TreeNode>>) -> i32 {
        let mut queue: VecDeque<&TreeNode> = VecDeque::new();
        let root_node = root.as_ref().unwrap();
        let mut current_node = root_node.as_ref();
        queue.push_back(current_node);

        while let Some(node) = queue.pop_front() {
            current_node = node;
            if let Some(ref left) = current_node.left {
                queue.push_back(left);
            }
            if let Some(ref right) = current_node.right {
                queue.push_back(right);
            }
        }

        current_node.data
    }
}

Swift

class Solution {
    func deepestNode(_ root: TreeNode?) -> Int {
        var queue: [TreeNode] = [root!]
        var currentNode = root!

        while !queue.isEmpty {
            currentNode = queue.removeFirst()
            if let left = currentNode.left {
                queue.append(left)
            }
            if let right = currentNode.right {
                queue.append(right)
            }
        }

        return currentNode.data
    }
}

Dart

import 'dart:collection';

class Solution {
  int deepestNode(TreeNode? root) {
    Queue<TreeNode> queue = Queue();
    TreeNode currentNode = root!;
    queue.add(currentNode);

    while (queue.isNotEmpty) {
      currentNode = queue.removeFirst();
      if (currentNode.left != null) queue.add(currentNode.left!);
      if (currentNode.right != null) queue.add(currentNode.right!);
    }

    return currentNode.data;
  }
}

C#

using System.Collections.Generic;

public class Solution {
    public int deepestNode(TreeNode root) {
        var queue = new Queue<TreeNode>();
        var currentNode = root;
        queue.Enqueue(currentNode);

        while (queue.Count > 0) {
            currentNode = queue.Dequeue();
            if (currentNode.left != null) queue.Enqueue(currentNode.left);
            if (currentNode.right != null) queue.Enqueue(currentNode.right);
        }

        return currentNode.data;
    }
}

PHP

class Solution {
    public function deepestNode(?TreeNode $root): int {
        $queue = [$root];
        $currentNode = $root;

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

        return $currentNode->data;
    }
}