Connect Nodes at the Same Level

Given a binary tree where each node has at most two children, your task is to connect all adjacent nodes at the same level. You should populate each node's 'next' pointer to its next right node. If there is no next right node, set the 'next' pointer to NULL. Initially, all 'next' pointers are NULL.

The node structure is defined 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. }

Example:

The left image shows the initial binary tree and the right image shows the binary tree after connecting adjacent nodes at the same level.

Connections would be as follows:

The 'next' pointer of the node with value 2 is connected to the node with value 3. The 'next' pointer of the node with value 4 is connected to the node with value 5. The 'next' pointer of the node with value 5 is connected to the node with value 6. Nodes with values 1, 3, and 6 have a 'next' pointer value of NULL.

Input:

The first line of input contains an integer ‘T’ denoting the number of test cases.

Then, for each test case, the first line contains elements in level order, separated by spaces. Use -1 for a null node.

Output:

For each test case, output each level's nodes as connected by 'next' pointers, with '#' marking the end of each level.

Constraints:

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

Note:

• The structure of the node is predefined and should not be altered.
• The root of the tree is known.
• There is at least one node in the binary tree.
• Use only constant extra space.