We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Nearest Right Node in Binary Tree

Number: 1745

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

Given the root of a binary tree and a target node u in the tree, return the nearest node on the same level that is to the right of u. If u is the rightmost node at its level, return null.

Key Insights

  • Utilize level-order traversal (BFS) to process nodes level by level.
  • When processing each level, upon encountering the target node u, the next node in that level (if it exists) is the answer.
  • If the target node is the last node in a level, there is no node to its right; return null.
  • This method ensures that all nodes in the same level are checked, keeping the solution clear and efficient.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes in the tree since every node is potentially visited once. Space Complexity: O(W), where W is the maximum number of nodes at any level (the tree's width).

Solution

The solution employs a Breadth-First Search (BFS) approach using a queue to traverse the tree level by level. For each level, the algorithm processes all nodes and checks if any of them is the target node u. If found, the subsequent node in that level (if present) is returned as the nearest right node. If u is the last node in its level, the function returns null. The approach efficiently handles edge cases, such as when u is the only node at its level.

Code Solutions

from collections import deque

# 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

def findNearestRightNode(root, u):
    # If the tree is empty, return None.
    if not root:
        return None
    
    # Initialize a queue for level-order traversal.
    queue = deque([root])
    
    while queue:
        level_length = len(queue)
        # Process nodes at the current level.
        for i in range(level_length):
            node = queue.popleft()
            # If the target node is found.
            if node is u:
                # Return the immediate next node in this level if present.
                return queue[0] if i < level_length - 1 else None
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return None
← Back to All Questions