1602. Find Nearest Right Node in Binary Tree
Problem Description
Given a binary tree (a tree where each node has at most two children), we need to find the nearest node to the right of a given node u
on the same level. If there is no node to the right of u
on the same level (meaning u
is the rightmost node), we should return null
. The problem requires us to consider the level of the nodes in the tree, which is the depth at which they are found, with the root node being at level one.
To understand the problem, let's consider an example:
1 1 2 / \ 3 2 3 4 / \ 5 4 5
If u
is node 2, the nearest right node on the same level is 3. If u
is node 4, the nearest right node is 5. If u
is node 5, since there are no further nodes to its right, the answer would be null
.
To get the solution, we need an approach that allows us to identify the nodes at each level and their order from left to right.
Flowchart Walkthrough
Let's analyze the problem using the flowchart. Here's a step-by-step walkthrough:
Is it a graph?
- Yes: Although it's a binary tree, a binary tree is a specific type of graph.
Is it a tree?
- Yes: The data structure in question is specifically mentioned to be a binary tree.
Is the problem related to directed acyclic graphs (DAGs)?
- No: While all trees are DAGs, the special properties of binary trees are more relevant here. Additionally, the problem does not involve typical DAG-related questions like ordering or dependency resolution.
Is the problem related to shortest paths?
- No: The task is to find the nearest right node at the same level, not a shortest path issue.
Does the problem involve connectivity?
- Yes: We are trying to determine a direct connection on the same level to the given node, which can be framed as a connectivity problem concerning nodes at a specific depth.
Is the graph weighted?
- No: Connectivity in this context does not involve weights.
Does the problem have small constraints?
- No: The size of the binary tree can be quite large, and the complexity of the problem focuses more on traversing levels efficiently rather than exploiting small size constraints.
Conclusion: The flowchart and analysis suggest using BFS for this problem to efficiently traverse and check nodes level by level in an unweighted tree, ensuring that we find the nearest right node in the most direct manner.
Intuition
The intuitive approach to solving this problem is to use Breadth-First Search (BFS). BFS is a graph traversal method that explores nodes level by level. For a binary tree, BFS starts at the root node, then explores all the children nodes, and so on down the levels of the tree. It is often implemented with a queue data structure.
In this context, BFS allows us to traverse the tree level by level, which aligns perfectly with the requirement to find nodes on the same level. By keeping track of nodes as we traverse each level, we can identify each node's immediate right neighbor on the same level.
The implementation of the solution initializes a queue with the root node. Then, it enters a loop that continues as long as there are nodes left to visit. Within this loop, we iterate over the number of elements that the queue has at the beginning of each iteration, which corresponds to all the nodes at the current level of the tree. We dequeue each of these nodes, checking if it matches the node u
. If we find the node u
, we return the next node in the queue, which will be u
's nearest right neighbor on the same level. If u
happens to be the last node on its level, the queue would be empty after it, so we return null
. If the current node has left or right children, these children are added to the queue to explore the next level on subsequent iterations.
By the end of the BFS process, we will have either found the nearest right neighbor of u
or determined that no such node exists, returning the correct result in either case.
Learn more about Tree, Breadth-First Search and Binary Tree patterns.
Solution Approach
The given solution uses Breadth-First Search (BFS), a classic algorithm for traversing or searching tree or graph data structures. Here's how it's applied in this case:
-
Initialization: First, a queue named
q
is initialized with the root node of the tree. This queue will be used to keep track of the nodes to visit next, starting from the root. In BFS, the queue is crucial for managing the order of exploration. -
Traversal: Then we enter a while loop which continues as long as there are nodes in the queue.
-
Level-wise Iteration: Inside the while loop, we have a for loop that runs as many times as there are elements in the queue at the start of the while loop iteration. This is to ensure that we only process nodes that are at the same level in each iteration.
- For each iteration, a node is popped from the left of the queue using
q.popleft()
. This operation ensures that we are visiting nodes from left to right at the current level—just like reading a text.
- For each iteration, a node is popped from the left of the queue using
-
Checking the Target Node:
- Within this for loop, we check if the popped node is the node
u
that we are trying to find the nearest right node for. - If the current node is
u
, we then return the next right neighbor if it exists. This is done by checking whether the for loop indexi
is zero. Ifi
is not zero, then it means there's another node at this level to the right ofu
, so we returnq[0]
, the next node. Ifi
is zero,u
is the last node on its level, so we returnnull
.
- Within this for loop, we check if the popped node is the node
-
Adding Child Nodes:
- If the current node is not
u
, we add its child nodes to the queue if they exist. This prepares the next level for exploration. First, the left child is added usingq.append(root.left)
and then the right child usingq.append(root.right)
.
- If the current node is not
-
Loop Continuation: The for loop ensures that all nodes on the same level are processed, after which the while loop moves on to the next level.
-
Completing the Search: If we never find the target node
u
(which shouldn't happen given the problem constraints), or there's no right node, the while loop will eventually end when there are no more nodes to process in the queue.
By implementing BFS, we ensure that we visit all nodes at each level from left to right, which is essential for finding the nearest right node to a given node u
on the same level.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Consider a binary tree as follows:
1 A 2 / \ 3 B C 4 / / \ 5D E F
We want to find the nearest right node of node B
.
Following the solution approach:
-
Initialization: We initialize a queue
q
and enqueue the root nodeA
. -
Traversal: We enter the while loop since our queue is not empty.
-
Level-wise Iteration: We have one element (the root
A
) in our queue, so the for loop inside the while loop will run once.- We dequeue node
A
fromq
and sinceA
is not our target nodeB
, we move forward.
- We dequeue node
-
Adding Child Nodes:
- We add
A
's child nodesB
andC
to the queue. Now our queue looks like:[B, C]
.
- We add
-
Loop Continuation: The for loop ends, and we go back to the start of the while loop. Now, the queue has two elements at this level,
B
andC
. -
Level-wise Iteration: The for loop inside the while loop will now run twice since there are two elements.
- We dequeue node
B
. This is our target node.
- We dequeue node
-
Checking the Target Node:
-
Since
B
is the target, we check if there's a right neighbor. Since we're not at the end of the level (the for loop has not finished all its iterations), we peek and see that the next element in the queue is nodeC
. -
We return
C
as the nearest right node toB
.
-
If our target was node C
, following similar steps, we would dequeue C
, and because there would be no next element in the queue at this level, we would return null
, indicating there is no right neighbor at the same level.
This walkthrough illustrates how Breadth-First Search can be used to navigate a binary tree level by level to return the nearest right node on the same level as the target node. If the target node is rightmost on its level, we correctly return null
.
Solution Implementation
1from collections import deque
2from typing import Optional
3
4# Definition for a binary tree node.
5class TreeNode:
6 def __init__(self, val=0, left=None, right=None):
7 self.val = val
8 self.left = left
9 self.right = right
10
11class Solution:
12 def findNearestRightNode(self, root: TreeNode, target_node: TreeNode) -> Optional[TreeNode]:
13 # Initialize the queue with the root node
14 queue = deque([root])
15
16 # Perform level order traversal using the queue
17 while queue:
18 # Iterate through the current level
19 for i in range(len(queue) - 1, -1, -1):
20 current_node = queue.popleft()
21
22 # Check if the currentNode is the targetNode
23 if current_node == target_node:
24 # Return the next node in the queue if it's not the last node in the level
25 return queue[0] if i else None
26
27 # Enqueue the child nodes of the current node
28 if current_node.left:
29 queue.append(current_node.left)
30 if current_node.right:
31 queue.append(current_node.right)
32 # If no right node is found, return None
33 return None
34
1class Solution {
2
3 /**
4 * Finds the nearest right node to node u in the same level.
5 *
6 * @param root The root of the binary tree.
7 * @param u The target node to find its nearest right node.
8 * @return The nearest right neighbor in the same level as u,
9 * or null if u is the rightmost node.
10 */
11 public TreeNode findNearestRightNode(TreeNode root, TreeNode u) {
12 // Create a queue to perform level order traversal of the tree.
13 Deque<TreeNode> queue = new ArrayDeque<>();
14
15 // Start from the root of the tree.
16 queue.offer(root);
17
18 // Perform level order traversal.
19 while (!queue.isEmpty()) {
20 // Process each level of the tree.
21 for (int i = queue.size(); i > 0; --i) {
22 // Dequeue node from the queue.
23 TreeNode currentNode = queue.pollFirst();
24
25 // Check if the current node is the target node u.
26 if (currentNode == u) {
27 // If not the last node in its level, return the next node, otherwise return null.
28 return i > 1 ? queue.peekFirst() : null;
29 }
30
31 // If current node has a left child, enqueue it.
32 if (currentNode.left != null) {
33 queue.offer(currentNode.left);
34 }
35
36 // If current node has a right child, enqueue it.
37 if (currentNode.right != null) {
38 queue.offer(currentNode.right);
39 }
40 }
41 }
42
43 // If the target node u is not found or does not have a right neighbor, return null.
44 return null;
45 }
46}
47
1class Solution {
2public:
3 // Finds the nearest node to the right of the given node 'u' at the same level in a binary tree
4 TreeNode* findNearestRightNode(TreeNode* root, TreeNode* u) {
5 // Initialize a queue to conduct a level-order traversal
6 queue<TreeNode*> nodeQueue;
7 nodeQueue.push(root);
8
9 // Execute the level-order traversal until the queue is empty
10 while (!nodeQueue.empty()) {
11 // Determine the number of nodes at the current level
12 int levelSize = nodeQueue.size();
13
14 // Iterate through all nodes at the current level
15 for (int i = 0; i < levelSize; ++i) {
16 // Access the front node in the queue
17 TreeNode* currentNode = nodeQueue.front();
18 nodeQueue.pop();
19
20 // Check if the current node is the target node 'u'
21 if (currentNode == u) {
22 // If the target node is not at the end of the level, return the next node
23 // Otherwise, return nullptr because there is no node to the right at the same level
24 return i < levelSize - 1 ? nodeQueue.front() : nullptr;
25 }
26
27 // Enqueue the left child if it exists
28 if (currentNode->left) {
29 nodeQueue.push(currentNode->left);
30 }
31
32 // Enqueue the right child if it exists
33 if (currentNode->right) {
34 nodeQueue.push(currentNode->right);
35 }
36 }
37 }
38
39 // If the target node 'u' is not found or does not have a right neighbor, return nullptr
40 return nullptr;
41 }
42};
43
1/**
2 * Definition for a binary tree node.
3 */
4class TreeNode {
5 val: number;
6 left: TreeNode | null;
7 right: TreeNode | null;
8
9 constructor(val: number = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
10 this.val = val;
11 this.left = left;
12 this.right = right;
13 }
14}
15
16/**
17 * Find the nearest right node to the given node `u` in the same level of a binary tree.
18 * @param {TreeNode} root - The root of the binary tree.
19 * @param {TreeNode} u - The target node to find the nearest right node for.
20 * @return {TreeNode | null} - The nearest right node or null if there's no such node.
21 */
22var findNearestRightNode = function (root: TreeNode, u: TreeNode): TreeNode | null {
23 // Queue to implement level-order traversal
24 const queue: TreeNode[] = [root];
25
26 // Execute a level-order traversal using a queue
27 while (queue.length) {
28 // Process all nodes on the current level
29 for (let i = queue.length; i > 0; --i) {
30 // Retrieve the front node from the queue
31 let currentNode: TreeNode = queue.shift()!;
32
33 // If the current node is the target node `u`
34 if (currentNode === u) {
35 // If this is not the last node of the level, return the next node
36 // Otherwise, return null
37 return i > 1 ? queue[0] : null;
38 }
39
40 // If the current node has a left child, enqueue it
41 if (currentNode.left) {
42 queue.push(currentNode.left);
43 }
44
45 // If the current node has a right child, enqueue it
46 if (currentNode.right) {
47 queue.push(currentNode.right);
48 }
49 }
50 }
51
52 // If the target node `u` was not found, return null
53 return null;
54};
55
Time and Space Complexity
The given code performs a level order traversal on a binary tree to find the nearest right node of a given node u
.
Time Complexity
The time complexity of the code is O(N)
where N
is the number of nodes in the binary tree. This is because every node in the tree is visited exactly once during the level order traversal.
Space Complexity
The space complexity of the code is also O(N)
. In the worst-case scenario (when the tree is a perfect binary tree), the maximum number of nodes at the last level of the tree will be around N/2
. Hence, the queue q
can potentially hold up to N/2
nodes, which simplifies to O(N)
when represented in Big O notation.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of these properties could exist for a graph but not a tree?
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
Binary Tree Min Depth Prereq BFS on Tree problems bfs_intro Given a binary tree find the depth of the shallowest leaf node https algomonster s3 us east 2 amazonaws com binary_tree_min_depth png Explanation We can solve this problem with either DFS or BFS With DFS we traverse the whole tree looking for leaf nodes and record and update the minimum depth as we go With BFS though since we search level by level we are guaranteed to find the shallowest leaf node
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.