[Python] O(n) time/ O(log n) space recursion, explained
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 a
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.\n\n![image](https://assets.leetcode.com/users/images/b838445a-d58e-420b-889e-208d6813beec_1605257150.2922277.png)\n\n\n**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!\n\n```\nclass Solution:\n    def connect(self, root):\n        if not root or not root.left: return root\n        \n        self.connect(root.left)\n        self.connect(root.right)\n        \n        lft = root.left\n        rgh = root.right\n        lft.next = rgh\n\n        while lft.right: \n            lft = lft.right\n            rgh = rgh.left\n            lft.next = rgh\n        \n        return root\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
['Recursion']