Problem statement

https://binarysearch.com/problems/Next-Node-on-Its-Right/

Solution

Traverse tree with bfs, then find node.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, root, target):
        if not root: return None
        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:
            for i, node in enumerate(level[:-1]):
                if node.val == target:
                    return level[i + 1]