Find Nearest Right Node in Binary Tree

medium tree bfs level order

Problem

Given the root of a binary tree and a target node value u, return the node that lies immediately to the right of u on the same level. If u is the rightmost node on its level, return null.

"Same level" means the same depth from the root. A breadth-first (level-order) traversal visits a level left to right, so the answer is simply the node dequeued right after u within the same level.

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

Output5

Level 3 reads left to right as 4, 5, 6. The node just right of 4 is 5.

level-order (use "null" for missing children)

from collections import deque

def find_nearest_right_node(root, u):
    queue = deque([root])
    while queue:
        size = len(queue)
        for i in range(size):
            node = queue.popleft()
            if node.val == u:
                return queue[0] if i < size - 1 else None
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return None

function findNearestRightNode(root, u) {
  const queue = [root];
  while (queue.length) {
    const size = queue.length;
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      if (node.val === u) {
        return i < size - 1 ? queue[0] : null;
      }
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }
  return null;
}

class Solution {
    public TreeNode findNearestRightNode(TreeNode root, int u) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.val == u) {
                    return i < size - 1 ? queue.peek() : null;
                }
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        return null;
    }
}

TreeNode* findNearestRightNode(TreeNode* root, int u) {
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front(); q.pop();
            if (node->val == u) {
                return i < size - 1 ? q.front() : nullptr;
            }
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
    return nullptr;
}

Explanation

The phrase "nearest node to the right on the same level" is exactly what a level-order (BFS) traversal exposes. We process the tree one full level at a time using a queue.

At the start of each level we record size, the number of nodes currently queued — these are precisely the nodes on this level. We then dequeue them one by one with an index i from 0 to size - 1.

When the dequeued node equals the target u, its right neighbor is the very next node on the level. If i < size - 1 the node is not the last on its level, so the neighbor is sitting at the front of the queue right now (we have not consumed it yet). Otherwise u is rightmost and the answer is null.

Returning queue[0] works because we enqueue children left to right; the front of the queue after dequeuing u is the node that was immediately to its right on the same level.

Example on [1,2,3,null,4,5,6] with u = 4: levels are [1], [2,3], [4,5,6]. On the third level i=0 dequeues 4, which is not last, so the front of the queue is 5 → answer 5.

Time: O(n) Space: O(n)