Find Nearest Right Node in Binary Tree

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

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);
        }
    }
};