1602. Find Nearest Right Node in Binary Tree

MediumTreeBreadth-First SearchBinary 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:

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.
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 index i is zero. If i is not zero, then it means there's another node at this level to the right of u, so we return q[0], the next node. If i is zero, u is the last node on its level, so we return null.
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 using q.append(root.left) and then the right child using q.append(root.right).
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 Evaluator

Example Walkthrough

Consider a binary tree as follows:

    A
   / \
  B   C
 /   / \
D   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 node A.
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 from q and since A is not our target node B, we move forward.
Adding Child Nodes:
- We add A's child nodes B and C to the queue. Now our queue looks like: [B, C].
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 and C.
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.
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 node C.
- We return C as the nearest right node to B.

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don’t know