Problem statement

https://leetcode.com/problems/find-nearest-right-node-in-binary-tree/

Solution

We can just use problem 102. Binary Tree Level Order Traversal and then find next element in level if we have or None if we do not have.

Complexity

Time complexity is O(n), space complexity also O(n). Space complexity can be improved to O(w) if we do early stopping.

Code

class Solution:
    def findNearestRightNode(self, root, u):
        queue, result = deque([root]), []
        
        while queue:
            level = []
            for i in range(len(queue)):
                node = queue.popleft()
                level.append(node)
                if node.left:  queue.append(node.left)
                if node.right: queue.append(node.right)
            result.append(level)
        
        for level in result:
            if u in level:
                idx = level.index(u)
                return None if idx == len(level) - 1 else level[idx + 1]