https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii

I spend some time for this problem, because my solution for problem 116 is quite different and can not be applied here (https://leetcode.com/problems/populating-next-right-pointers-in-each-node/discuss/934066/Python-O(n)-time-O(log-n)-space-recursion-explained). So, we need to think of something different here.

The main idea is to go level by level and use already existing .next connections: if you will not do it, problem will be quite painful. So, idea is the following:

  1. We will keep two nodes: node and curr: first one is for parent level and curr for next level.
  2. We check if we have node.left and if we have, we create connection curr.next = node.left and also move our curr to the right, so it always will be the rightest visited node in level.
  3. In similar way we check if we have node.right and do the same for it.
  4. When we finished with node, we move it to right: node = node.next.
  5. Finally, we need to go to the next level: we update node = dummy.next.

Note, that in this place we will have some extra connections from dummy variables to left side of our tree, but there is no way testing system can detect it, because it is one-way connections. If you want to be completely honest, you need to add just one more line dummy.next = None after the line node = dummy.next.

Complexity: time complexity is O(n): we visit each node of our tree only once. Space complexity is O(1)

class Solution:
    def connect(self, root):
        node = root
        while node:
            curr = dummy = Node(0)
            while node:
                if node.left:
                    curr.next = node.left
                    curr = curr.next
                if node.right:
                    curr.next = node.right
                    curr = curr.next
                node = node.next
            node = dummy.next
               
        return root

If you like the solution, you can upvote it on leetcode discussion section: Problem 0117