Leetcode 0116. Populating Next Right Pointers in Each Node

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

In this problem we are given that our tree is perfect binary tree, which will help us a lot. Let us use recursion: imagine, that for left and right subtees we already make all connections, what we need to connect now? See the image and it will become very clear: we need to connect just O(log n) pairs now: we go the the left and to the right children. Then from left children we go as right as possible and from right children we go as left as possible.

Complexity: time complexity can be found, using Master theorem: F(n) = 2*F(n/2) + log n, from here F(n) = O(n). Space complexity is O(log n), because we use recursion. Note, that space complexity can be reduced to O(1), because we know the structure of our tree!

class Solution:
    def connect(self, root):
        if not root or not root.left: return root
        
        self.connect(root.left)
        self.connect(root.right)
        
        lft = root.left
        rgh = root.right
        lft.next = rgh

        while lft.right: 
            lft = lft.right
            rgh = rgh.left
            lft.next = rgh
        
        return root

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