Find Nearest Right Node in Binary Tree

Updated on 28 May, 2025
Find Nearest Right Node in Binary Tree header image

Problem Statement

Given a binary tree and a specific node u within the tree, the task is to determine the nearest node on the same tree level but situated immediately on the right side of node u. If node u does not have any nodes to its right on the same level, the function should return null. This scenario tests understanding and manipulation of tree data structures, focusing on level-order traversal to identify positional relationships among nodes.

Examples

Example 1

Input:

root = [1,2,3,null,4,5,6], u = 4

Output:

5

Explanation:

The nearest node on the same level to the right of node 4 is node 5.

Example 2

Input:

root = [3,null,4,2], u = 2

Output:

null

Explanation:

There are no nodes to the right of 2.

Constraints

  • The number of nodes in the tree is in the range [1, 105].
  • 1 <= Node.val <= 105
  • All values in the tree are distinct.
  • u is a node in the binary tree rooted at root.

Approach and Intuition

To solve this problem efficiently, we can employ a breadth-first traversal (BFT) using a queue. This traversal method ensures that nodes are processed level by level from left to right, which is ideal for checking neighbors on the same level:

  1. Start by initializing a queue and pushing the root of the tree alongside its level index (e.g., (root, 0)). The level index helps in determining when we move to a new level in the tree.
  2. Use a loop to process each node and its level from the queue:
    • For each node extracted, check if this node matches the target node u.
    • If it matches and there's a subsequent node within the same level in the queue, that node is our answer—return it.
    • If it matches but no subsequent node exists in the same level, return null.
    • Push the current node's children to the queue with an incremented level index.
  3. If the loop completes without finding node u, return null as the node doesn't exist in the tree based on given constraints.

This approach effectively checks each node's right neighbor by leveraging the natural left-to-right processing of nodes within the same level in a BFT. Use of a queue guarantees that each node and its immediate right neighbor (if it exists) are checked consecutively.

Edge Case Considerations:

  • If u is the only node at its level, or positioned at the end (i.e., no nodes to its right), the function should return null.
  • Efficient handling is pivotal, given the high potential number of nodes (up to 100,000), which mandates an algorithm efficient both in terms of time (ideally O(n)) and space.

Solutions

  • C++
  • Java
  • Python
cpp
class Solution {
private:
    int search_depth;
    TreeNode* subsequent_node;
    TreeNode* search_target;

public:
    TreeNode* locateAdjacentRightNode(TreeNode* root, TreeNode* target) {
        this->search_depth = -1;
        this->search_target = target;
        this->subsequent_node = nullptr;
        traverse(root, 0);
        return this->subsequent_node;
    }

    void traverse(TreeNode* current, int level) {
        if (current == this->search_target) {
            this->search_depth = level;
            return;
        }

        if (level == this->search_depth) {
            if (this->subsequent_node == nullptr) {
                this->subsequent_node = current;
            }
            return;
        }

        if (current->left != nullptr) {
            traverse(current->left, level + 1);
        }
        if (current->right != nullptr) {
            traverse(current->right, level + 1);
        }
    }
};

This C++ solution defines a class Solution that provides the functionality to find the nearest right node of a given target node in a binary tree. The critical class members include search_depth, subsequent_node, and search_target, used during the traversal of the binary tree.

  • The locateAdjacentRightNode function initializes the search parameters and begins the tree traversal starting from the root node with an intial level of 0.
  • The traverse function performs a recursive depth-first search through the tree. During traversal:
    • It checks if the current node matches the target node and updates the search_depth.
    • If the current level matches search_depth and subsequent_node is not set, it captures the current node as the nearest right node.
    • Recursively moves to the left and right children of the current node, incrementing the level by 1 each time to accurately track the depth of traversal.

By maintaining a targeted search level (search_depth) and updating the nearest right node (subsequent_node), the algorithm efficiently identifies the right neighboring node in relation to a specified target node within the binary tree.

java
class Solution {

    private int nodeDepth;
    private TreeNode siblingNode, soughtNode;

    public TreeNode findNearestRightNode(TreeNode root, TreeNode u) {
        nodeDepth = -1;
        soughtNode = u;
        siblingNode = null;
        traverse(root, 0);
        return siblingNode;
    }

    public void traverse(TreeNode currentNode, int depth) {
        if (currentNode == soughtNode) {
            nodeDepth = depth;
            return;
        }

        if (depth == nodeDepth) {
            if (siblingNode == null) siblingNode = currentNode;
            return;
        }

        if (currentNode.left != null) traverse(currentNode.left, depth + 1);
        if (currentNode.right != null) traverse(currentNode.right, depth + 1);
    }
}

In this solution, you are tasked with finding the nearest right node to a given node u in a binary tree. This code defines a Java class named Solution which includes two primary functions to accomplish this task.

Here's a breakdown of the implemented functionality:

  • Global Variables:

    • nodeDepth - stores the depth of the node u.
    • siblingNode - holds the nearest right node found during the traversal.
    • soughtNode - stores the reference to the node u for which the nearest right node is sought.
  • findNearestRightNode(TreeNode root, TreeNode u):

    • Initializes the global variables.
    • Begins the tree traversal with the root node at depth 0.
    • Returns the siblingNode, which will either be the nearest right node to u or null if no such node is found at the same depth.
  • traverse(TreeNode currentNode, int depth):

    • Handles the tree traversal recursively.
    • Checks if the current node is the sought-after node u. If so, it captures the depth and stops further operations in this branch (via return).
    • If currently at the depth of u and the siblingNode is not yet found, sets the siblingNode as currentNode.
    • Recursively calls itself for left and right children of the current node, incrementing the depth for each.

This method efficiently finds the nearest right node at the same depth as node u without additional data structures like queues. However, it relies on the recursive stack, and its performance depends on the height and structure of the binary tree. It’s a direct and straightforward approach, leveraging depth-first search principles.

python
class Solution:
    def findNextRightNode(self, root: TreeNode, target: TreeNode) -> TreeNode:
        def traverse(node, level):
            nonlocal target_level, right_node
            if node == target:
                target_level = level
                return
            if level == target_level:
                if right_node is None:
                    right_node = node
                return
            if node.left:
                traverse(node.left, level + 1)
            if node.right:
                traverse(node.right, level + 1)

        target_level, right_node = -1, None
        traverse(root, 0)
        return right_node

The provided Python code defines a solution for finding the nearest right node of a given target node within a binary tree. The solution uses a depth-first traversal approach to explore the tree and identify the target node and its corresponding right neighbor at the same depth. Here's how the code accomplishes this task:

  • The findNextRightNode function expects two parameters: root, the root node of the binary tree, and target, the node for which you want to find the nearest right node.

  • Inside findNextRightNode, the nested helper function traverse is defined. This function performs the actual traversal and comparison. It takes node, representing the current node being processed, and level, indicating its depth within the tree.

  • Two non-local variables, target_level and right_node, track the level of the target node and the earliest visited node at the same level to the right of the target, respectively.

  • As traverse executes, it first checks if the current node matches the target. If it does, it updates target_level with the current level of the target.

  • If the current level matches target_level and right_node is unset, right_node gets updated to point to this node, marking it as the nearest right node.

  • The exploration continues to the left and right children of the current node, incrementing the level by 1 to reflect the move down the tree.

  • Finally, findNextRightNode initializes target_level and right_node and invokes traverse starting from the root node at level 0. The result stored in right_node (either a node or None if no right node is found) is returned as the output.

When using this code:

  • Ensure that the TreeNode class is appropriately defined elsewhere in your environment, as it represents the structure of nodes in your binary tree.
  • The function expects a binary tree and operates correctly under the assumption of a consistent tree structure without cycles.

This solution efficiently finds the closest right node to a given target node without traversing unnecessary parts of the tree, leveraging depth-first search (DFS) to maintain optimal space and time complexity given the problem constraints.

Comments

No comments yet.