Solution Explanation: Finding the Nearest Right Node in a Binary Tree

The problem asks to find the nearest node to the right of a given node u at the same level in a binary tree. If no such node exists (i.e., u is the rightmost node at its level), the function should return null.

Two approaches are presented: Breadth-First Search (BFS) and Depth-First Search (DFS). Both achieve the same result, but differ in their traversal strategy and consequently, their code structure and space complexity.

Approach 1: Breadth-First Search (BFS)

BFS is ideal for level-order traversal. We use a queue to process nodes level by level. The algorithm works as follows:

1. Initialization: Enqueue the root node into a queue.
2. Level Traversal: Iterate while the queue is not empty. For each level, process nodes one by one.
3. Node Check: If the current node is u:
   • If there are more nodes in the queue (meaning u is not the rightmost node), return the next node in the queue.
   • Otherwise, return null.
4. Enqueue Children: Add the left and right children of the current node to the queue.

Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node at most once. Space Complexity: O(W), where W is the maximum width (maximum number of nodes at any level) of the tree. In the worst case (a complete binary tree), W can be O(N).

Approach 2: Depth-First Search (DFS)

DFS uses recursion to traverse the tree. It keeps track of the depth and the node u.

1. Initialization: Set d (depth) to 0 and ans (result) to null. d tracks the depth of u when found.
2. Recursive Traversal: The dfs function recursively visits nodes.
3. Depth Check: If the current depth i is equal to d, then the current node is the rightmost node encountered at that level so far. We update ans.
4. u Check: If the current node is u, we record its depth in d.
5. Recursive Calls: Recursively call dfs for the left and right children.

Time Complexity: O(N). Each node is visited at most once. Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H can be O(N), but for balanced trees, it's typically O(log N).

Code Examples (Python3)

BFS:

from collections import deque
 
def findNearestRightNode(root, u):
    q = deque([root])
    while q:
        for i in range(len(q)):
            curr = q.popleft()
            if curr == u:
                return q[0] if i < len(q) else None
            if curr.left:
                q.append(curr.left)
            if curr.right:
                q.append(curr.right)
    return None

DFS:

def findNearestRightNode(root, u):
    d = 0
    ans = None
 
    def dfs(node, level):
        nonlocal d, ans
        if not node or ans:
            return
        if level == d:
            ans = node
            return
        if node == u:
            d = level
            return
        dfs(node.left, level + 1)
        dfs(node.right, level + 1)
 
    dfs(root, 1)
    return ans
 

The code examples in other languages (Java, C++, Go, JavaScript) follow similar logic, adapting the data structures and syntax specific to each language. Choose the approach that best suits your needs based on the expected tree structure and space complexity considerations. For most cases, BFS is generally preferred due to its consistent space complexity regardless of tree balance.