Connect next pointers for each tree level

You are given the root of a binary tree where each node has fields left, right, and next (initially null). For every node, set its next pointer to the node immediately to its right on the same level. If there is no node to the right, set next = null.

Constraints/requirements:

• The tree is not necessarily perfect or complete.
• Aim for O(n) time.
• Use O(1) extra space beyond the recursion/iteration variables (i.e., do not use a queue for BFS).

Return the root after populating all next pointers.

Connect Next Pointers for Each Tree Level

You are given a binary tree where every non-null node conceptually has four fields: val, left, right, and next (initially null). Set each node's next pointer to the node immediately to its right on the same level. If there is no such node, its next pointer should remain null.

The tree is not necessarily perfect or complete.

For this coding problem, the input tree is provided as a level-order array using heap-style indexing: for a node at index i, its left child is at 2*i + 1 and its right child is at 2*i + 2. Missing nodes are represented by None.

Because pointer-based trees are hard to compare directly in automated tests, return a flat serialization of the tree after connecting next pointers. Serialize level by level by following only next pointers, and append the string '#' after each level.

Example:

• Input: [1, 2, 3, 4, 5, None, 7]
• After linking: 1 -> null, 2 -> 3 -> null, 4 -> 5 -> 7 -> null
• Output: [1, '#', 2, 3, '#', 4, 5, 7, '#']

Aim for O(n) time and O(1) auxiliary space for the pointer-connection step.

Hints

1. Once one level is connected, you can traverse that entire level using next pointers instead of a queue.
2. While scanning the current level, build the next level's linked list using a dummy head and a moving tail pointer.