Jobs

Interviews

Discussions

Find Nearest Right Node in Binary Tree

Medium

Google

1 view

Topics:

TreesGraphs

Problem

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

If there is no node u in the tree, return null.

Example

Consider the following binary tree:

If u is node 2, the nearest right node is 3.
If u is node 4, the nearest right node is 5.
If u is node 5, the nearest right node is null.
If u is node 6, the nearest right node is null.
If u is node 1, the nearest right node is null.

Clarifications

What should I return if the tree is empty?
What should I return if node u is null?
Are the values of the nodes unique?
Does the tree has to be complete?

Find Nearest Right Node in Binary Tree

Medium

Google

1 view

Topics:

TreesGraphs

Problem

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

If there is no node u in the tree, return null.

Example

Consider the following binary tree:

If u is node 2, the nearest right node is 3.
If u is node 4, the nearest right node is 5.
If u is node 5, the nearest right node is null.
If u is node 6, the nearest right node is null.
If u is node 1, the nearest right node is null.

Clarifications

What should I return if the tree is empty?
What should I return if node u is null?
Are the values of the nodes unique?
Does the tree has to be complete?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What should be returned if the input node is the rightmost node at its level, meaning it has no nearest right node?
Can the binary tree be empty? If so, what should I return?
Is the input node guaranteed to be present in the binary tree?
Are the values in the binary tree unique, or can there be duplicate values?
By 'nearest right node', do you mean the first node to the right on the same level in a level-order traversal?

Brute Force Solution

Approach

The brute force method involves examining every single node in the tree until we locate the target node. Once found, we explore the tree level by level to find the nearest node to its right.

Here's how the algorithm would work step-by-step:

Start by searching the entire tree, looking at each node one by one, until you find the node you are looking for.
Once you find the node, begin exploring the tree level by level, starting from the root.
At each level, check if the target node has a right neighbor. If so, return this neighbor as the answer.
If the target node does not have a right neighbor on that level, continue exploring the next level down the tree.
Keep going until you've either found the nearest right node or exhausted all the nodes in the tree.
If you reach the end of the tree without finding a right neighbor, then there is no nearest right node.

Code Implementation

def find_nearest_right_node_brute_force(root, target):
    if not root:
        return None

    target_node = None
    queue = [root]
    while queue:
        node = queue.pop(0)
        if node == target:
            target_node = node
            break
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

    if not target_node:
        return None

    queue = [root]

    while queue:
        level_size = len(queue)

        for i in range(level_size):
            node = queue.pop(0)

            # Found target node, check for right neighbor
            if node == target:
                if i + 1 < level_size:
                    return queue[0]
                else:
                    pass

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    return None

Big(O) Analysis

Time Complexity

O(n) – The brute force approach first searches the entire tree to find the target node, which takes O(n) time in the worst case, where n is the number of nodes in the tree. After finding the target, a level-order traversal (BFS) is performed, which also takes O(n) time in the worst case as every node might need to be visited. Since these operations are performed sequentially, the overall time complexity is O(n) + O(n), which simplifies to O(n).

Space Complexity

O(W) – The brute force method described uses level-order traversal to explore the tree. This traversal requires a queue to store the nodes at each level, where W is the maximum width of the binary tree. In the worst-case scenario (a complete binary tree), the width at the bottom level could be approximately N/2, where N is the total number of nodes in the tree. Therefore, the auxiliary space used by the queue is proportional to the maximum width of the tree. This leads to a space complexity of O(W).

Optimal Solution

Approach

We need to find the node immediately to the right of a target node at the same level in a binary tree. The best way is to explore the tree level by level, so that when we find our target, the next node we see is our answer.

Here's how the algorithm would work step-by-step:

Start exploring the tree level by level, like reading a book line by line.
Keep track of the nodes on the current level.
Check each node on the current level to see if it's the target node.
If you find the target node, the next node on the same level is the answer. If there isn't a next node, then there is no nearest right node.
If you don't find the target node on the current level, move on to exploring the next level of the tree.

Code Implementation

from collections import deque

def find_nearest_right_node(root, target):
    if not root:
        return None

    queue = deque([root])

    while queue:
        level_length = len(queue)
        
        # Iterate through all nodes at the current level
        for i in range(level_length):
            current_node = queue.popleft()

            # Check if the current node is the target
            if current_node == target:
                # If it's the last node, return None
                if i == level_length - 1:
                    return None
                # Otherwise, the next node is the answer
                else:
                    return queue[0]

            # Add children to the queue for the next level
            if current_node.left:
                queue.append(current_node.left)
            if current_node.right:
                queue.append(current_node.right)

    return None

Big(O) Analysis

Time Complexity

O(n) – The algorithm uses a level-order traversal (breadth-first search) to explore the binary tree. In the worst-case scenario, the algorithm visits every node in the tree to either find the target or determine that it doesn't exist, where n is the number of nodes in the tree. Therefore, the time complexity is proportional to the number of nodes, resulting in O(n). The level-order traversal ensures each node is visited at most once.

Space Complexity

O(W) – The described level-by-level traversal, often implemented using a queue for breadth-first search, stores nodes at the current level. In the worst-case scenario, the queue holds all nodes at the widest level of the tree. Therefore, the auxiliary space used is proportional to the maximum width (W) of the binary tree, where W represents the maximum number of nodes at any level. Consequently, the space complexity is O(W).

Edge Cases

Case	How to Handle
Root is null	Return null immediately as there are no nodes in the tree.
Target node is null	Return null, as the search target is invalid.
Target node is the rightmost node on its level	Return null because there is no right node on the same level.
Target node is not present in the tree	Return null since no right neighbor exists for a non-existent target.
Tree consists of only the root node (target is root)	Return null, as the root node has no siblings.
Tree is a skewed tree (all nodes are left or right children)	If the target is in the skewed structure, its right neighbor will be null or not present in the level, returning null accordingly.
Tree contains duplicate values, and target value appears multiple times	The solution should return the right neighbor of the first instance of the target node found at the target's level during a level order traversal.
Very large tree exceeding memory constraints for level order traversal	Consider iterative deepening depth-first search approach with level information to reduce memory footprint.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What should be returned if the input node is the rightmost node at its level, meaning it has no nearest right node?
Can the binary tree be empty? If so, what should I return?
Is the input node guaranteed to be present in the binary tree?
Are the values in the binary tree unique, or can there be duplicate values?
By 'nearest right node', do you mean the first node to the right on the same level in a level-order traversal?

Brute Force Solution

Approach

The brute force method involves examining every single node in the tree until we locate the target node. Once found, we explore the tree level by level to find the nearest node to its right.

Here's how the algorithm would work step-by-step:

Start by searching the entire tree, looking at each node one by one, until you find the node you are looking for.
Once you find the node, begin exploring the tree level by level, starting from the root.
At each level, check if the target node has a right neighbor. If so, return this neighbor as the answer.
If the target node does not have a right neighbor on that level, continue exploring the next level down the tree.
Keep going until you've either found the nearest right node or exhausted all the nodes in the tree.
If you reach the end of the tree without finding a right neighbor, then there is no nearest right node.

Code Implementation

def find_nearest_right_node_brute_force(root, target):
    if not root:
        return None

    target_node = None
    queue = [root]
    while queue:
        node = queue.pop(0)
        if node == target:
            target_node = node
            break
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

    if not target_node:
        return None

    queue = [root]

    while queue:
        level_size = len(queue)

        for i in range(level_size):
            node = queue.pop(0)

            # Found target node, check for right neighbor
            if node == target:
                if i + 1 < level_size:
                    return queue[0]
                else:
                    pass

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    return None

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start exploring the tree level by level, like reading a book line by line.
Keep track of the nodes on the current level.
Check each node on the current level to see if it's the target node.
If you find the target node, the next node on the same level is the answer. If there isn't a next node, then there is no nearest right node.
If you don't find the target node on the current level, move on to exploring the next level of the tree.

Code Implementation

from collections import deque

def find_nearest_right_node(root, target):
    if not root:
        return None

    queue = deque([root])

    while queue:
        level_length = len(queue)
        
        # Iterate through all nodes at the current level
        for i in range(level_length):
            current_node = queue.popleft()

            # Check if the current node is the target
            if current_node == target:
                # If it's the last node, return None
                if i == level_length - 1:
                    return None
                # Otherwise, the next node is the answer
                else:
                    return queue[0]

            # Add children to the queue for the next level
            if current_node.left:
                queue.append(current_node.left)
            if current_node.right:
                queue.append(current_node.right)

    return None

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Root is null	Return null immediately as there are no nodes in the tree.
Target node is null	Return null, as the search target is invalid.
Target node is the rightmost node on its level	Return null because there is no right node on the same level.
Target node is not present in the tree	Return null since no right neighbor exists for a non-existent target.
Tree consists of only the root node (target is root)	Return null, as the root node has no siblings.
Tree is a skewed tree (all nodes are left or right children)	If the target is in the skewed structure, its right neighbor will be null or not present in the level, returning null accordingly.
Tree contains duplicate values, and target value appears multiple times	The solution should return the right neighbor of the first instance of the target node found at the target's level during a level order traversal.
Very large tree exceeding memory constraints for level order traversal	Consider iterative deepening depth-first search approach with level information to reduce memory footprint.