Given the root of a perfect binary treeA binary tree in which all the levels are completely filled with nodes, and all leaf nodes (nodes with no children) are at the same level., where each node is equipped with an additional pointer, next, connect all nodes from left to right. Do so in such a way that the next pointer of each node points to its immediate right sibling except for the rightmost node, which points to the first node of the next level.

The next pointer of the last node of the binary tree (i.e., the rightmost node of the last level) should be set to NULL.

Constraints:

• The number of nodes in the tree is in the range $[0, 500]$.

• $-1000 \leq$ Node.data $\leq 1000$

The algorithm connects all nodes by utilizing the structure of the perfect binary tree, where each non-leaf node has exactly two children. Using this property, the algorithm connects nodes without needing extra space. It uses two pointers: one to traverse the current level and another to connect nodes at the next level. Starting from the root, the algorithm links each node’s left child to its right child and then connects the right child to the next node’s left child on the same level, continuing this process across all nodes at that level. If no adjacent node is on the same level, the right child’s next pointer is connected to the first node on the next lower level. This process continues until all nodes are connected in a manner that reflects level-order traversal.

The steps of the algorithm are given below:

1. If the root is None, the tree is empty. In this case, return immediately.

2. Initialize two pointers current and last to the root node. The current pointer traverses the nodes level by level, while the last keeps track of the last node connected via the next pointer.

3. The loop continues as long as current.left exists. In a perfect binary tree, all non-leaf nodes have a left child, so this condition ensures that the loop continues until all levels are processed.

   1. First connection: last.next = current.left connects the last node (initially the root) to the current.left child. After this, last is updated to current.left.

   2. Second connection: last.next = current.right connects current.left (now pointed to by last) to current.right. last is then updated to current.right.

   3. Move to the next node: current = current.next moves the current pointer to the next node.

4. Finally, return the modified root of the tree, where all nodes are connected to their next sibling in the level-order traversal.

Let’s look at the following illustration to get a better understanding of the solution: