Find Nearest Right Node in Binary Tree solution and explanation
Google
5 more videos on this problem
1602. Find Nearest Right Node in Binary Tree (Leetcode Medium)Programming Live with Larry · 5:33 · 188 views
algorithm leetcode 1602 Find nearest right node in binary treeRoy Son · 4:14 · 75 views
Leetcode Medium (Challenge) | 1602 - Find Nearest Right Node in Binary Tree | JAVADuctileChart · 21:47 · 45 views
ทำโจทย์ Leetcode: Find Nearest Right Node in Binary TreeTP Coder · 14:26 · 33 views
Leetcode 1602AUM · 21:01 · 19 views
LeetCode 1602: Find Nearest Right Node in Binary TreeAlitaCode · 28:55
The problem
Given the root of a binary tree and a node u in the tree, return the nearest node on the same level that is to the right of u, or return null if u is the rightmost node in its level.
Example 1:
Input: root = [1,2,3,null,4,5,6], u = 4 Output: 5 Explanation: The nearest node on the same level to the right of node 4 is node 5.
Example 2:
Input: root = [3,null,4,2], u = 2 Output: null Explanation: There are no nodes to the right of 2.
Constraints:
- The number of nodes in the tree is in the range
[1, 105]. 1 <= Node.val <= 105- All values in the tree are distinct.
uis a node in the binary tree rooted atroot.
Approach overview
Problem Overview: You are given the root of a binary tree and a target node u. The task is to return the node immediately to the right of u on the same level. If u is the rightmost node in its level, return null. The challenge is identifying nodes that share the same depth while preserving their left‑to‑right order.
Approach 1: Breadth-First Search (Level Order) (Time: O(n), Space: O(n))
This problem maps directly to level order traversal using a queue. Perform a standard Breadth-First Search on the Binary Tree. For each level, track the number of nodes currently in the queue. Iterate through that level from left to right. When you encounter the target node u, check whether it is the last node in the current level. If not, the next node in the queue is the nearest right node. If it is the last node, return null. This works because BFS processes nodes level by level, preserving their natural left-to-right ordering.
The key insight is that the queue already maintains the correct order of nodes at each depth. No extra bookkeeping is required beyond the level size. Each node is visited exactly once, producing O(n) time complexity with O(n) auxiliary space for the queue in the worst case.
Approach 2: Depth-First Search with Level Tracking (Time: O(n), Space: O(n))
A Depth-First Search can also solve the problem by explicitly tracking depth. Traverse the tree and store nodes grouped by their level using a list or hash map keyed by depth. While performing DFS, append each node to the container corresponding to its level. After traversal, locate the level containing node u, then scan that level’s list to find the element immediately after it.
This approach separates traversal from lookup. The DFS builds a level structure first, then a quick index lookup determines the nearest right node. Time complexity remains O(n) since every node is visited once, and space complexity is also O(n) due to the storage of nodes across levels.
Recommended for interviews: The BFS level-order traversal is the expected approach. It aligns naturally with the problem’s definition of "same level" and identifies the neighbor in a single pass without storing all nodes. Showing the DFS variant demonstrates deeper understanding of tree traversal patterns, but BFS communicates the optimal reasoning most clearly.
Approach 1: BFS
We can use Breadth-First Search, starting from the root node. When we reach node u, we return the next node in the queue.
The time complexity is O(n), and the space complexity is O(n). Where n is the number of nodes in the binary tree.
# 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]:
q = deque([root])
while q:
for i in range(len(q) - 1, -1, -1):
root = q.popleft()
if root == u:
return q[0] if i else None
if root.left:
q.append(root.left)
if root.right:
q.append(root.right)/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode findNearestRightNode(TreeNode root, TreeNode u) {
Deque<TreeNode> q = new ArrayDeque<>();
q.offer(root);
while (!q.isEmpty()) {
for (int i = q.size(); i > 0; --i) {
root = q.pollFirst();
if (root == u) {
return i > 1 ? q.peekFirst() : null;
}
if (root.left != null) {
q.offer(root.left);
}
if (root.right != null) {
q.offer(root.right);
}
}
}
return null;
}
}/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* findNearestRightNode(TreeNode* root, TreeNode* u) {
queue<TreeNode*> q{{root}};
while (q.size()) {
for (int i = q.size(); i; --i) {
root = q.front();
q.pop();
if (root == u) {
return i > 1 ? q.front() : nullptr;
}
if (root->left) {
q.push(root->left);
}
if (root->right) {
q.push(root->right);
}
}
}
return nullptr;
}
};/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {TreeNode} u
* @return {TreeNode}
*/
var findNearestRightNode = function (root, u) {
const q = [root];
while (q.length) {
for (let i = q.length; i; --i) {
root = q.shift();
if (root == u) {
return i > 1 ? q[0] : null;
}
if (root.left) {
q.push(root.left);
}
if (root.right) {
q.push(root.right);
}
}
}
return null;
};/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func findNearestRightNode(root *TreeNode, u *TreeNode) *TreeNode {
q := []*TreeNode{root}
for len(q) > 0 {
for i := len(q); i > 0; i-- {
root = q[0]
q = q[1:]
if root == u {
if i > 1 {
return q[0]
}
return nil
}
if root.Left != nil {
q = append(q, root.Left)
}
if root.Right != nil {
q = append(q, root.Right)
}
}
}
return nil
}Approach 2: DFS
DFS performs a pre-order traversal of the binary tree. The first time we search to node u, we mark the current depth d. The next time we encounter a node at the same level, it is the target node.
The time complexity is O(n), and the space complexity is O(n). Where n is the number of nodes in the binary tree.
# 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]:
def dfs(root, i):
nonlocal d, ans
if root is None or ans:
return
if d == i:
ans = root
return
if root == u:
d = i
return
dfs(root.left, i + 1)
dfs(root.right, i + 1)
d = 0
ans = None
dfs(root, 1)
return ans/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private TreeNode u;
private TreeNode ans;
private int d;
public TreeNode findNearestRightNode(TreeNode root, TreeNode u) {
this.u = u;
dfs(root, 1);
return ans;
}
private void dfs(TreeNode root, int i) {
if (root == null || ans != null) {
return;
}
if (d == i) {
ans = root;
return;
}
if (root == u) {
d = i;
return;
}
dfs(root.left, i + 1);
dfs(root.right, i + 1);
}
}/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* findNearestRightNode(TreeNode* root, TreeNode* u) {
TreeNode* ans;
int d = 0;
function<void(TreeNode*, int)> dfs = [&](TreeNode* root, int i) {
if (!root || ans) {
return;
}
if (d == i) {
ans = root;
return;
}
if (root == u) {
d = i;
return;
}
dfs(root->left, i + 1);
dfs(root->right, i + 1);
};
dfs(root, 1);
return ans;
}
};/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {TreeNode} u
* @return {TreeNode}
*/
var findNearestRightNode = function (root, u) {
let d = 0;
let ans = null;
function dfs(root, i) {
if (!root || ans) {
return;
}
if (d == i) {
ans = root;
return;
}
if (root == u) {
d = i;
return;
}
dfs(root.left, i + 1);
dfs(root.right, i + 1);
}
dfs(root, 1);
return ans;
};/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func findNearestRightNode(root *TreeNode, u *TreeNode) *TreeNode {
d := 0
var ans *TreeNode
var dfs func(*TreeNode, int)
dfs = func(root *TreeNode, i int) {
if root == nil || ans != nil {
return
}
if d == i {
ans = root
return
}
if root == u {
d = i
return
}
dfs(root.Left, i+1)
dfs(root.Right, i+1)
}
dfs(root, 1)
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| BFS | – |
| DFS | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| BFS Level Order Traversal | O(n) | O(n) | Best general solution when you need neighbors within the same tree level |
| DFS with Level Storage | O(n) | O(n) | Useful when DFS traversal is already required or when storing nodes grouped by depth |
Frequently asked questions
Is Find Nearest Right Node in Binary Tree easy or hard?
The problem is generally classified as Medium difficulty. The main challenge is recognizing that the nearest right node must exist in the same level, which naturally leads to a BFS level-order traversal strategy.
Find Nearest Right Node in Binary Tree Python/Java solution
Most implementations use a queue for BFS. Push the root into the queue, process nodes level by level, and track the number of nodes per level. When the target node appears, return the next node in the queue if it belongs to the same level. The same logic translates directly to Python, Java, C++, Go, and JavaScript.
How to solve Find Nearest Right Node in Binary Tree in O(n)?
Use a BFS level-order traversal. For each level, record the number of nodes currently in the queue. When the target node is encountered, return the next node in that level if it exists; otherwise return null. This guarantees a single pass through all nodes.
What is the best approach for Find Nearest Right Node in Binary Tree?
Breadth-First Search (level order traversal) is the most efficient and intuitive approach. Process the tree level by level using a queue. When the target node appears, check if another node exists in the same level immediately after it. This solution runs in O(n) time and O(n) space.
Is Find Nearest Right Node in Binary Tree asked at Google/Amazon/Meta?
Binary tree traversal problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. Variants that require level-order traversal or neighbor detection in trees are especially common in system design and algorithm rounds.
What data structure is used in Find Nearest Right Node in Binary Tree?
A queue is the primary data structure for the optimal BFS solution. It maintains nodes in level order so neighbors at the same depth appear sequentially. The DFS alternative may use recursion and a hash map or list to group nodes by depth.
What is the time complexity of Find Nearest Right Node in Binary Tree?
The optimal solution runs in O(n) time because each node in the binary tree is visited once during traversal. Space complexity is O(n) in the worst case due to the queue used in BFS or the level storage used in DFS.