LeetCode 1602 - Find Nearest Right Node in Binary Tree

LeetCode Problem 1602

Difficulty: 🟡 Medium
Topics: Tree, Breadth-First Search, Binary Tree

Solution

Problem Understanding

This problem asks us to find the nearest node to the right of a given node u on the same level of a binary tree.

A binary tree is organized into levels. The root is on level 0, its children are on level 1, their children are on level 2, and so on. For a given node u, we want to locate the next node that appears immediately to its right within the same level.

The important detail is that we are not looking for the next node in an inorder traversal, preorder traversal, or any DFS ordering. We specifically care about level ordering, which naturally suggests a breadth first traversal.

The input consists of:

• root, the root node of the binary tree
• u, a reference to a node that exists somewhere inside the tree

The output should be:

• The nearest node to the right of u on the same level
• null if u is already the rightmost node in that level

The constraints are important:

• The tree can contain up to 10^5 nodes
• All node values are distinct
• u is guaranteed to exist in the tree

Because the tree can become very large, any algorithm worse than linear time risks timing out. This immediately rules out solutions that repeatedly scan large portions of the tree.

Several edge cases are important:

• u may already be the rightmost node in its level
• The tree may contain only one node
• The tree may be extremely unbalanced
• u may appear at the deepest level
• Some nodes may have only one child

The problem guarantees that u exists in the tree, so we never need to handle the case where the target node is absent.

Approaches

Brute Force Approach

A straightforward brute force idea is to first determine the level of node u, then collect all nodes on that level, and finally locate the node immediately after u.

One way to do this is:

1. Perform a DFS to determine the depth of u
2. Perform another traversal to gather all nodes at that depth
3. Scan the collected nodes to find u
4. Return the next node if it exists

This approach is correct because it explicitly reconstructs the entire target level and searches within it. However, it performs unnecessary work because it may traverse large parts of the tree multiple times.

In the worst case, the tree may contain 10^5 nodes, so repeated traversals increase overhead. While still technically linear overall if carefully implemented, it is more complicated and less efficient in practice than a direct BFS solution.

Optimal Approach

The key observation is that breadth first search naturally processes the tree level by level.

When performing BFS:

• All nodes of one level are processed before moving to the next level
• Nodes are visited from left to right within a level

This means that when we encounter node u during a level traversal:

• The next node in the queue for that same level is exactly the nearest right node
• If u is the last node in the level, then no such node exists

This makes BFS the ideal technique for the problem.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Multiple traversals and extra bookkeeping
Optimal	O(n)	O(w)	Single BFS traversal, where w is maximum tree width

Algorithm Walkthrough

Optimal BFS Algorithm

1. Initialize a queue and place the root node into it.

The queue allows us to process nodes level by level in left to right order. This ordering is exactly what the problem requires. 2. Start a loop that continues while the queue is not empty.

Each iteration of this outer loop processes one complete level of the tree. 3. Record the current queue size.

This size tells us how many nodes belong to the current level. It is important because child nodes added during processing belong to the next level and should not be mixed into the current one. 4. Process all nodes in the current level one by one.

Remove nodes from the front of the queue. 5. For each node, check whether it is equal to u.

Since the problem gives us the actual node reference, we compare node objects directly rather than comparing values. 6. If the current node is u:

• If it is not the last node in the current level, the next node in the queue is the nearest right node
• If it is the last node in the level, return None

7. Add the current node's left and right children to the queue if they exist.

These nodes belong to the next level and will be processed later. 8. If BFS finishes without returning, return None.

This situation technically cannot happen because u is guaranteed to exist.

Why it works

Breadth first search processes nodes level by level from left to right. At any moment during level processing, the queue contains the remaining nodes of the current level followed by future levels. Therefore, when we encounter u, the next node in the current level processing order is exactly the nearest node to its right. If u is the last node of that level, no such node exists.

Python Solution

from collections import deque
from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def findNearestRightNode(
        self,
        root: TreeNode,
        u: TreeNode
    ) -> Optional[TreeNode]:

        queue = deque([root])

        while queue:
            level_size = len(queue)

            for i in range(level_size):
                current = queue.popleft()

                if current == u:
                    if i == level_size - 1:
                        return None
                    return queue[0]

                if current.left:
                    queue.append(current.left)

                if current.right:
                    queue.append(current.right)

        return None

The implementation follows the BFS algorithm directly.

A deque is used because it provides efficient O(1) insertion and removal operations from both ends. This is ideal for queue behavior.

The outer while loop processes the tree level by level. At the start of each level, level_size stores the number of nodes belonging to that level.

The inner loop iterates exactly level_size times. This guarantees that we only process nodes from the current level during that iteration.

When we encounter node u, we determine whether it is the last node in the level by checking:

i == level_size - 1

If this condition is true, there is no node to the right, so we return None.

Otherwise, the next node in the queue is the nearest right node, so we return:

queue[0]

Children are appended to the queue after processing the current node, ensuring proper BFS ordering.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func findNearestRightNode(root *TreeNode, u *TreeNode) *TreeNode {
    queue := []*TreeNode{root}

    for len(queue) > 0 {
        levelSize := len(queue)

        for i := 0; i < levelSize; i++ {
            current := queue[0]
            queue = queue[1:]

            if current == u {
                if i == levelSize-1 {
                    return nil
                }
                return queue[0]
            }

            if current.Left != nil {
                queue = append(queue, current.Left)
            }

            if current.Right != nil {
                queue = append(queue, current.Right)
            }
        }
    }

    return nil
}

The Go implementation mirrors the Python logic closely.

Instead of using a deque, Go uses a slice to simulate a queue. Removing the front element is done with:

queue = queue[1:]

Node comparisons use pointer equality:

current == u

This works because u is an actual node reference from the tree.

Go uses nil instead of Python's None.

Worked Examples

Example 1

Input:

root = [1,2,3,null,4,5,6]
u = 4

Tree structure:

        1
       / \
      2   3
       \ / \
       4 5 6

We perform BFS level by level.

Step	Queue Before Processing	Current Node	Action
1	[1]	1	Add 2, 3
2	[2, 3]	2	Add 4
3	[3, 4]	3	Add 5, 6
4	[4, 5, 6]	4	Found u

At this moment:

• 4 is not the last node in the level
• The next node in the queue is 5

So the answer is:

5

Example 2

Input:

root = [3,null,4,2]
u = 2

Tree structure:

    3
     \
      4
     /
    2

BFS traversal:

Step	Queue Before Processing	Current Node	Action
1	[3]	3	Add 4
2	[4]	4	Add 2
3	[2]	2	Found u

Node 2 is the last node in its level, so there is no node to its right.

Result:

null

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is visited exactly once
Space	O(w)	Queue stores at most one level at a time

The BFS traversal processes every node once, so the runtime is linear in the number of nodes.

The space usage depends on the maximum width of the tree. In the worst case, a complete binary tree may have roughly n / 2 nodes in the last level, so the worst case auxiliary space becomes O(n).

Test Cases

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def findNearestRightNode(self, root, u):
        queue = deque([root])

        while queue:
            level_size = len(queue)

            for i in range(level_size):
                current = queue.popleft()

                if current == u:
                    if i == level_size - 1:
                        return None
                    return queue[0]

                if current.left:
                    queue.append(current.left)

                if current.right:
                    queue.append(current.right)

        return None

sol = Solution()

# Example 1
n4 = TreeNode(4)
n5 = TreeNode(5)
n6 = TreeNode(6)
n2 = TreeNode(2, None, n4)
n3 = TreeNode(3, n5, n6)
n1 = TreeNode(1, n2, n3)

assert sol.findNearestRightNode(n1, n4) == n5  # nearest right exists

# Example 2
n2b = TreeNode(2)
n4b = TreeNode(4, n2b, None)
n3b = TreeNode(3, None, n4b)

assert sol.findNearestRightNode(n3b, n2b) is None  # rightmost node

# Single node tree
single = TreeNode(1)

assert sol.findNearestRightNode(single, single) is None  # only node

# Complete tree
a4 = TreeNode(4)
a5 = TreeNode(5)
a6 = TreeNode(6)
a7 = TreeNode(7)
a2 = TreeNode(2, a4, a5)
a3 = TreeNode(3, a6, a7)
a1 = TreeNode(1, a2, a3)

assert sol.findNearestRightNode(a1, a5) == a6  # across subtrees
assert sol.findNearestRightNode(a1, a7) is None  # last node in level

# Left skewed tree
l4 = TreeNode(4)
l3 = TreeNode(3, l4, None)
l2 = TreeNode(2, l3, None)
l1 = TreeNode(1, l2, None)

assert sol.findNearestRightNode(l1, l3) is None  # single node level

# Right skewed tree
r4 = TreeNode(4)
r3 = TreeNode(3, None, r4)
r2 = TreeNode(2, None, r3)
r1 = TreeNode(1, None, r2)

assert sol.findNearestRightNode(r1, r3) is None  # single node level

# Sparse tree
s7 = TreeNode(7)
s5 = TreeNode(5, None, s7)
s4 = TreeNode(4)
s3 = TreeNode(3, s4, None)
s2 = TreeNode(2, None, s5)
s1 = TreeNode(1, s2, s3)

assert sol.findNearestRightNode(s1, s4) == s7  # sparse structure

Test	Why
Example 1	Validates standard nearest-right lookup
Example 2	Validates rightmost node handling
Single node tree	Tests smallest possible input
Complete tree	Tests normal balanced traversal
Complete tree, last node	Ensures null return for level end
Left skewed tree	Tests levels containing one node
Right skewed tree	Tests asymmetric structure
Sparse tree	Tests missing children handling

Edge Cases

Single Node Tree

A tree containing only one node is the smallest valid input. In this case, the node has no neighbors on its level. A careless implementation might incorrectly access an empty queue after processing the node. The solution handles this correctly because the node is recognized as the last node in its level and immediately returns None.

Target Node Is Rightmost in Its Level

This is the most important edge case in the problem. If u is the final node in its level, there is no valid answer. The implementation explicitly checks:

i == level_size - 1

This guarantees that we never incorrectly return a node from the next level.

Sparse Trees With Missing Children

Binary trees are not always complete. Some nodes may have only one child or no children. A naive implementation that assumes both children always exist could crash or produce incorrect ordering. The solution safely checks:

if current.left:

and

if current.right:

before adding children to the queue.

Extremely Deep Trees

The tree may contain up to 10^5 nodes and may become heavily skewed. Recursive DFS solutions risk stack overflow in languages with limited recursion depth. The iterative BFS approach avoids recursion entirely, making it safe for very deep trees.