Leetcode: Populating next right pointer

Populating Next Right Pointers in Each Node | LeetCode OJ

We need to connect each node with the node to its right on the same level.We can follow the following step to do this recursively

1. Connect the left child to the right child
2. For right child find the next node of parent
3. Connect right child to the left child of next node of parent

Remarks:

1. O(1) space complexity, as no values are being stored
2. O(n/2) time complexity as It will be executed for all nodes who have children i.e. all non-leaf nodes

# Definition for binary tree with next pointer.
# class TreeLinkNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None
class Solution(object):
    def connect(self, root):
        """
        :type root: TreeLinkNode
        :rtype: nothing
        """
        if root and root.left:
            root.left.next = root.right
            if root.next:
                root.right.next = root.next.left
            self.connect(root.left)
            self.connect(root.right)