Find Nearest Right Node in Binary Tree

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.

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.

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.