Problem:

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node { int val; Node *left; Node *right; Node *next; } Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Follow up:

You may only use constant extra space. Recursive approach is fine, you may assume implicit stack space does not count as extra space for this problem. Example 1: Input: root = [1,2,3,4,5,null,7] Output: [1,#,2,3,#,4,5,7,#] Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

Approach:

The approach to this problem is to use level order traversal with constant space. We can start by initializing the next pointer of the root node to null and creating a pointer current to the leftmost node of the tree. We can have a pointer level that points to the current node's level and iteratively move to the next level of the tree until we reach the last level. At each node, we can connect its left and right nodes and keep updating the next pointer of the node. If the next node is not present, then we can update the next pointer to null. We can continue iterating over the level and updating the next pointers until we reach the last level.

Algorithm:

1. Initialize variables current and level to root and null respectively.

2. While current is not null, perform the following steps:

   a) Set temp to null.

   b) While current is not null:

    i) If the current's left node is not null, connect it to temp and update temp to point to the left node.
   
    ii) If current's right node is not null, connect it to temp and update temp to point to the right node.
   
    iii) Update current to point to its next node.
   

   c) Update current to point to the leftmost node of the next level using the level pointer.

   d) Update level to null.

3. Return root.

Time Complexity:

The time complexity of this algorithm is O(n), where n is the number of nodes in the binary tree. This is because we traverse each node of the binary tree once.

Space Complexity:

The space complexity of this algorithm is O(1), as we only use constant extra space. We do not use any additional data structures to store the nodes of the tree.

Implementation:

Here is the implementation of the above algorithm in Python:

Definition for a Node.

class Node:

def init(self, val=0, left=None, right=None, next=None):

self.val = val

self.left = left

self.right = right

self.next = next

class Solution: def connect(self, root: 'Node') -> 'Node': if not root: return root

    current = root
    level = None
    
    while current:
        temp = None
        while current:
            if current.left:
                if temp:
                    temp.next = current.left
                else:
                    level = current.left
                temp = current.left
                    
            if current.right:
                if temp:
                    temp.next = current.right
                else:
                    level = current.right
                temp = current.right
                    
            current = current.next
                
        current = level
        level = None
        
    return root

The code above uses a nested while loop to traverse each level of the binary tree. We connect the left and right nodes of each node to update the next pointers and move the current pointer to the next node in the current level. We also update the level pointer to move to the next level of the tree. Finally, we return the root of the binary tree with the next pointers updated.

1