Link Neighbors across Missing Binary-Tree Children
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
For an arbitrary binary tree, set each node's `next` pointer to the node immediately to its right on the same level. Set the last next pointer on each level to null. All next pointers begin as null. Children may be missing; the tree need not be perfect or complete.
The original custom `Node` has `val`, `left`, `right`, and `next` fields:
```cpp
Node* connect(Node* root);
```
Modify the existing next links and return the root, retaining the tree's child structure.
### Examples
```text
Input tree: [8,3,12,null,5,10,null,4,null,null,11]
Levels read through next links: [8,#,3,12,#,5,10,#,4,11,#]
```
The last level connects nodes with different parents across missing child positions. `#` denotes the end of a next chain.
```text
Input tree: []
Output: []
```
### Constraints
- The tree contains between 0 and 6000 nodes.
- Node values lie between -100 and 100, inclusive.
- Every next field is initially null.
### Optional follow-up
Use only constant extra space. A recursive approach is allowed; its implicit stack space does not count as extra space for this problem.
Overview: Populate next-right links in a sparse binary tree by building each next level with head and tail pointers.
