Given the root of a binary tree root, each node contains pointers left, right, and an additional pointer next. Populate every node’s next pointer so that it points to the node immediately to its right on the same level. If there is no node to the right on that level, set next to null.

Return the root root after updating all next pointers.

Note: You must use only constant extra space. A recursive solution is allowed, and the implicit recursion stack does not count as extra space.

Constraints:

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

• $-100 \leq$ Node.val $\leq 100$

Input: root = [10,5,15,3,null,null,18]-TreeNode
Output: [10,#,5,15,#,3,18,#]-TreeNode
Explanation: Connecting nodes horizontally level by level gives level 0: 10 -> null, level 1: 5 -> 15 -> null, and level 2: 3 -> 18 -> null (3’s sibling is missing, so it connects across to 18).

Input: root = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]-TreeNode
Output: [1,#,2,3,#,4,5,6,7,#,8,9,10,11,12,13,14,15,#]-TreeNode
Explanation: Each level becomes a linked list from left to right: level 0: 1 -> null, level 1: 2 -> 3 -> null, level 2: 4 -> 5 -> 6 -> 7 -> null, and level 3: 8 -> 9 -> 10 -> 11 -> 12 -> 13 -> 14 -> 15 -> null.

Input: root = [-2,-3,4,null,-5,2,null,null,null,1,3]-TreeNode
Output: [-2,#,-3,4,#,-5,2,#,1,3,#]-TreeNode
Explanation: Even with missing children, next pointers connect to the next available node on the same level: level 0: -2 -> null, level 1: -3 -> 4 -> null, level 2: -5 -> 2 -> null (skipping over missing nodes), and level 3: 1 -> 3 -> null.

Input: root = [0]-TreeNode
Output: [0,#]-TreeNode
Explanation: Only one node exists, so its next pointer is null.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.