1602. Find Nearest Right Node in Binary Tree

MediumTreeBreadth-First SearchBinary Tree
Leetcode Link

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.

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

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:

  1. 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.

  2. Traversal: Then we enter a while loop which continues as long as there are nodes in the queue.

  3. 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.

  4. 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.

  5. 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).

  6. 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.

  7. 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.

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

How does merge sort divide the problem into subproblems?

Example 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:

  1. Initialization: We initialize a queue q and enqueue the root node A.

  2. Traversal: We enter the while loop since our queue is not empty.

  3. 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.

  4. Adding Child Nodes:

    • We add A's child nodes B and C to the queue. Now our queue looks like: [B, C].

  5. 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.

  6. 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.

  7. 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
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which data structure is used in a depth first search?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which type of traversal does breadth first search do?

Recommended Readings

Everything About Trees

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

BFS Fundamentals

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

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 Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ