Connect Nodes at Same Level Problem Statement

Given a binary tree, connect all adjacent nodes at the same level by populating each node's '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 the next pointers are set to NULL.

The structure of the tree node is as follows:

class BinaryTreeNode {
 int data; // Value of the node.
 BinaryTreeNode *left; // Pointer to left child node.
 BinaryTreeNode *right; // Pointer to right child node.
 BinaryTreeNode *next;  // Pointer to next right node at same level.
}

Input:

T
Then T test cases follow, each having:
Level order traversal of the nodes, with '-1' denoting a NULL node.

Output:

For each test case, print the level order as connected by the next pointers,
with '#' indicating the end of each level.

Example:

Input:

1
1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Output:

1 #
2 3 #
4 5 6 #
7 #

Explanation:

The tree will be connected as follows:

• The 'next' pointer of node with value 2 connects to node with value 3.
• The 'next' pointer of node with value 4 connects to node with value 5.
• The 'next' pointer of node with value 5 connects to node with value 6.
• Nodes with values 1, 3, and 6 will have their 'next' pointers set to NULL.

Constraints:

• 1 <= T <= 100
• 1 <= N <= 3000
• -10^9 <= DATA <= 10^9

Time Limit: 1 second.

Note:

• The structure of the node should not be altered.
• The root of the tree is known.
• The binary tree contains at least one node.
• It is allowed to use only constant extra space.