Code Implementation

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

from collections import deque

class Solution:
    def findNearestRightNode(self, root: 'TreeNode', u: 'TreeNode') -> 'TreeNode':
        if not root:
            return None
        queue = deque([root])
        while queue:
            size = len(queue)
            for i in range(size):
                node = queue.popleft()
                if node == u:
                    if i == size - 1:
                        return None
                    else:
                        return queue[0]
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return None
      

// Definition for a binary tree node.
// struct TreeNode {
//     int val;
//     TreeNode *left;
//     TreeNode *right;
//     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
// };

#include <queue>

class Solution {
public:
    TreeNode* findNearestRightNode(TreeNode* root, TreeNode* u) {
        if (!root) return nullptr;
        std::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 == u) {
                    if (i == size - 1) return nullptr;
                    else return q.front();
                }
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        return nullptr;
    }
};
      

// Definition for a binary tree node.
// public class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//     TreeNode(int x) { val = x; }
// }

import java.util.*;

class Solution {
    public TreeNode findNearestRightNode(TreeNode root, TreeNode u) {
        if (root == null) return null;
        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 == u) {
                    if (i == size - 1) return null;
                    else return queue.peek();
                }
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        return null;
    }
}
      

/**
 * // Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * @param {TreeNode} root
 * @param {TreeNode} u
 * @return {TreeNode}
 */
var findNearestRightNode = function(root, u) {
    if (!root) return null;
    let queue = [root];
    while (queue.length) {
        let size = queue.length;
        for (let i = 0; i < size; i++) {
            let node = queue.shift();
            if (node === u) {
                if (i === size - 1) return null;
                else return queue[0];
            }
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
    }
    return null;
};
      

Problem Description

Given a binary tree and a specific node u in that tree, you are asked to find the nearest node to the right of u on the same level. If u is the rightmost node at its level, return null.

• The binary tree is not necessarily complete or balanced.
• Each node value is unique, but you are given a direct reference to the node u (not just its value).
• There is only one valid solution for each input.
• You must not reuse or modify elements in the tree.

Your function should return the node object that is immediately to the right of u at the same depth, or null if no such node exists.

Thought Process

The heart of this problem is finding the "neighbor" of a given node at the same level in a binary tree. The most direct way to do this is to traverse the tree level by level (using Breadth-First Search, or BFS), so that we can easily see the nodes at each depth in order.

A brute-force approach might involve traversing the entire tree, recording each level's nodes, and then searching for u to find its right neighbor. However, this would require extra space to store all nodes by level, which is unnecessary.

Instead, we can optimize by processing the tree level by level, and as soon as we find u, we know that the next node in the current level (if any) is its nearest right node. If u is the last node in its level, there is no right neighbor.

By using a queue (for BFS), we can efficiently process each level and immediately determine the right neighbor without storing all nodes.

Solution Approach

Here is a step-by-step breakdown of the algorithm:

1. Initialize a Queue:
   • Start by putting the root node into a queue. This queue will help us process nodes level by level.
2. Process Each Level:
   • For each level, determine how many nodes are in that level by checking the queue's length at the start of the level.
3. Iterate Through the Level:
   • For each node in the current level, dequeue it from the queue.
   • If the node is u, check if it is the last node in the level:
     • If yes, return null (no right neighbor).
     • If not, the next node in the queue is the nearest right node; return it.
   • If the node is not u, enqueue its left and right children (if they exist).
4. Repeat:
   • Continue this process until the queue is empty or until u is found and its nearest right node is returned.

This method is efficient because it only traverses each node once, and does not require extra space to store all nodes at each level.

Example Walkthrough

Consider the following binary tree:

        1
       / \
      2   3
     /   / \
    4   5   6
  

Suppose u is the node with value 5.

1. Level 0: [1]
   Node 1 is not u. Enqueue 2 and 3.
2. Level 1: [2, 3]
   Node 2 is not u. Enqueue 4.
   Node 3 is not u. Enqueue 5 and 6.
3. Level 2: [4, 5, 6]
   Node 4 is not u.
   Node 5 is u. Since there is still one node left in the current level (6), return node 6 as the answer.

If u were node 6, since it is the last node in its level, the function would return null.

Time and Space Complexity

• Brute-force approach:
  • Time Complexity: O(N), where N is the number of nodes (since we have to traverse the whole tree).
  • Space Complexity: O(N), for storing each level's nodes in a separate data structure.
• Optimized BFS approach (used here):
  • Time Complexity: O(N), since each node is enqueued and dequeued at most once.
  • Space Complexity: O(W), where W is the maximum width of the tree (the largest number of nodes at any level), because that's the most nodes that will be in the queue at any one time.

The optimized solution is efficient for both time and space, making it suitable for large trees.

Summary

To find the nearest right node of a given node u in a binary tree, we use a level-order traversal (BFS) to process nodes level by level. This allows us to immediately identify the right neighbor of u when we encounter it. The approach is both time and space efficient, requiring only a queue and handling each node once. This strategy elegantly solves the problem by leveraging the natural structure of a BFS traversal to align with the problem's requirements.