Problem Description

You are given a binary tree with a root node and a specific node u that exists somewhere in the tree. Your task is to find the node that is immediately to the right of node u on the same level (depth) in the tree.

The key requirements are:

• The target node must be on the same level as node u (same distance from the root)
• The target node must be the nearest node to the right of u on that level
• If u is the rightmost node on its level, return null

For example, if you have a binary tree where nodes on level 3 from left to right are [A, B, u, C, D], and u is the given node, then the answer would be node C since it's the immediate right neighbor of u on the same level.

The solution uses a level-order traversal (BFS) approach with a queue. It processes nodes level by level, and when it encounters node u, it checks if there are more nodes remaining in the current level. If yes, the next node in the queue is the answer; if no (meaning u is the last node in its level), it returns null.

The clever part of the implementation is using a reverse loop range(len(q) - 1, -1, -1) to track how many nodes remain in the current level. When i reaches 0, it means u is the rightmost node of its level.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A binary tree is a special type of graph with nodes and edges (parent-child relationships).

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree.

DFS?

• Not necessarily: While DFS could work, let's reconsider. The problem asks for finding a node on the same level as node u. This is a strong hint that we need level-order traversal, which is characteristic of BFS rather than DFS.

Let me re-evaluate from the graph node:

Is it a graph?

• Yes: A binary tree is a graph.

Is it a tree?

• No (taking alternate path): Although it's technically a tree, the problem's requirement to find nodes on the same level suggests we should explore other graph algorithms.

Is the problem related to directed acyclic graphs?

• No: While a tree is a DAG, the problem isn't about topological ordering.

Is the problem related to shortest paths?

• No: We're not finding shortest paths; we're finding a specific node on the same level.

Does the problem involve connectivity?

• No: We're not checking if nodes are connected or finding connected components.

Does the problem have small constraints?

• No: The problem doesn't specify small constraints, and we need an efficient solution.

BFS?

• Yes: BFS is perfect for level-order traversal, which naturally processes all nodes at the same depth before moving to the next level.

Conclusion: The flowchart leads us to BFS (Breadth-First Search) as the optimal approach. BFS processes nodes level by level, making it ideal for finding the nearest right node on the same level as node u. When we encounter node u during our level-order traversal, we can immediately check if there's another node in the current level's queue, which would be the answer.

Intuition

When we need to find a node that's on the same level as another node, we should think about how to traverse the tree level by level. This immediately points us toward BFS (Breadth-First Search), which naturally processes all nodes at depth 0, then all nodes at depth 1, then depth 2, and so on.

The key insight is that in a standard BFS traversal using a queue, at any given moment during processing of a level, the queue contains exactly the nodes of the current level being processed, followed by nodes of the next level that have been discovered so far.

Here's the clever part: when we're processing nodes level by level, if we find node u, we know that:

1. If there are still unprocessed nodes in the current level (in the queue), the very next node must be the nearest right neighbor
2. If u is the last node being processed in this level, then it's the rightmost node and we return null

To track whether we're at the last node of a level, we can process each level completely before moving to the next. We do this by recording the queue size at the start of each level - this tells us exactly how many nodes belong to the current level. As we process each node and decrement our counter, we know precisely when we've reached the last node of the level.

The implementation uses a reverse loop for i in range(len(q) - 1, -1, -1) which counts down from the number of nodes in the current level. When we find u and i > 0, we know there are more nodes in this level, so we return the next node in the queue. When i == 0, node u is the last node in its level, so we return null.

Learn more about Tree, Breadth-First Search and Binary Tree patterns.

Solution Approach

The solution implements a level-order traversal using BFS with a queue data structure. Here's how the algorithm works:

1. Initialize the queue: Start with a deque containing only the root node: q = deque([root])

2. Process levels iteratively: The outer while q: loop continues as long as there are nodes to process.

3. Process each level completely: For each level, we use for i in range(len(q) - 1, -1, -1) to process exactly the nodes that belong to the current level. The key insight is that len(q) at the start of each iteration tells us how many nodes are in the current level.

4. Check for the target node: For each node processed:

   • Pop the leftmost node from the queue: root = q.popleft()
   • Check if this is our target node u: if root == u:
   • If it is node u:
     • If i > 0, there are still nodes remaining in the current level, so return q[0] (the next node in the queue, which is the nearest right neighbor)
     • If i == 0, node u is the last node in this level, so return None

5. Add children for next level: After checking each node, add its children to the queue for processing in the next level:

   if root.left:
       q.append(root.left)
   if root.right:
       q.append(root.right)

The algorithm guarantees that when we find node u, all nodes to its left on the same level have already been processed and removed from the queue, while any nodes to its right on the same level are still in the queue. The very first element in the queue at that moment is the nearest right node.

Time Complexity: O(n) where n is the number of nodes in the tree, as we might need to traverse all nodes in the worst case.

Space Complexity: O(w) where w is the maximum width of the tree, which represents the maximum number of nodes at any level stored in the queue.

Example Walkthrough

Let's walk through a concrete example to understand how the algorithm finds the right neighbor of a given node.

Consider this binary tree:

        1
       / \
      2   3
     / \   \
    4   5   6
   /
  7

Task: Find the right neighbor of node u = 5 (which should be node 6).

Step-by-step execution:

Initial state: q = deque([1]) (queue contains only root)

Level 1 (root level):

• Queue at start: [1], level size = 1
• Process node 1 (i = 0):
  • Pop node 1 from queue
  • Not our target node u
  • Add children: queue becomes [2, 3]

Level 2:

• Queue at start: [2, 3], level size = 2
• Process node 2 (i = 1):
  • Pop node 2 from queue
  • Not our target node u
  • Add children: queue becomes [3, 4, 5]
• Process node 3 (i = 0):
  • Pop node 3 from queue
  • Not our target node u
  • Add children: queue becomes [4, 5, 6]

Level 3:

• Queue at start: [4, 5, 6], level size = 3
• Process node 4 (i = 2):
  • Pop node 4 from queue
  • Not our target node u
  • Add children: queue becomes [5, 6, 7]
• Process node 5 (i = 1):
  • Pop node 5 from queue
  • This is our target node u!
  • Check: i = 1 > 0, so there are more nodes in this level
  • Return q[0] which is node 6 ✓

Result: The algorithm correctly returns node 6 as the right neighbor of node 5.

Alternative scenario: If we were looking for the right neighbor of node 6 instead:

• When we reach node 6 at level 3, i would equal 0 (last node in level)
• The algorithm would return None since node 6 is the rightmost node on its level

The key insight is that the counter i tells us exactly how many nodes remain unprocessed in the current level, allowing us to determine if our target node has a right neighbor or not.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm uses BFS (Breadth-First Search) to traverse the binary tree level by level. In the worst case, we need to visit every node in the tree exactly once before finding the target node u or determining its nearest right node. Each node is processed once - dequeued from the queue, checked against u, and its children are enqueued. Therefore, the time complexity is O(n), where n is the number of nodes in the binary tree.

Space Complexity: O(n)

The space complexity is determined by the maximum size of the queue q during execution. In the worst case, the queue needs to store all nodes at the widest level of the tree. For a complete binary tree, the last level contains approximately n/2 nodes, making the space complexity O(n). Additionally, the algorithm doesn't use any other data structures that scale with input size, so the overall space complexity remains O(n), where n is the number of nodes in the binary tree.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Confusing Node Position with Queue Position

The Problem: A common mistake is assuming that after finding node u, the next node in the queue is always the right neighbor. This fails when u is the last node of its level because the queue would then contain nodes from the next level.

Incorrect Implementation:

def findNearestRightNode(self, root: TreeNode, u: TreeNode) -> Optional[TreeNode]:
    queue = deque([root])
  
    while queue:
        current = queue.popleft()
      
        if current == u:
            # WRONG: This could return a node from the next level!
            return queue[0] if queue else None
          
        if current.left:
            queue.append(current.left)
        if current.right:
            queue.append(current.right)
  
    return None

The Solution: Track level boundaries explicitly by processing exactly level_size nodes per iteration:

while queue:
    level_size = len(queue)  # Capture current level size
  
    for i in range(level_size):  # Process only this level's nodes
        current = queue.popleft()
      
        if current == u:
            # Check if more nodes exist in THIS level
            return queue[0] if i < level_size - 1 else None
      
        # Add children for next level
        if current.left:
            queue.append(current.left)
        if current.right:
            queue.append(current.right)

Pitfall 2: Not Handling Edge Cases Properly

The Problem: Forgetting to handle special cases like:

• When u is the root node (no right neighbor possible at level 0)
• When u doesn't exist in the tree
• When the tree is empty or None

Incomplete Implementation:

def findNearestRightNode(self, root: TreeNode, u: TreeNode) -> Optional[TreeNode]:
    # Missing null check for root
    queue = deque([root])  # Crashes if root is None
  
    while queue:
        # ... rest of code

The Solution: Add proper validation:

def findNearestRightNode(self, root: TreeNode, u: TreeNode) -> Optional[TreeNode]:
    # Handle edge cases
    if not root or not u:
        return None
  
    # Special case: if u is root, it has no right neighbor at its level
    if root == u:
        return None
  
    queue = deque([root])
    # ... rest of implementation

Pitfall 3: Using Wrong Loop Index Check

The Problem: Using the wrong comparison when checking if there are more nodes in the current level. The original solution description mentions using range(len(q) - 1, -1, -1) and checking i > 0, but this is actually more complex than needed.

Confusing Implementation:

for i in range(len(queue) - 1, -1, -1):  # Reverse iteration
    current = queue.popleft()
  
    if current == u:
        return queue[0] if i > 0 else None  # Confusing: why i > 0?

The Solution: Use forward iteration with clear indexing:

level_size = len(queue)

for i in range(level_size):  # Forward iteration: 0, 1, 2, ...
    current = queue.popleft()
  
    if current == u:
        # Clear check: am I the last node in this level?
        return queue[0] if i < level_size - 1 else None

This makes it immediately clear that we're checking if the current position i is less than the last position level_size - 1.