hardTreesPure DSA~35 min
Connect Each Node to Its Right Neighbor
In a possibly imperfect binary tree, wire every node's next pointer to the node immediately to its right on the same level, using only constant extra space.
Problem
Given the root of a binary tree where each node has an additional next pointer (initially null), set each next pointer to the next node on the same level, or null if there is none. The tree is not necessarily perfect. Use O(1) extra space (aside from the implicit recursion-free traversal).
Input
A binary tree root with nodes carrying left, right, and next pointers.
Output
The same tree with next pointers populated.
Constraints
- 0 <= number of nodes <= 6000
- -100 <= node value <= 100
- Use constant extra space.
Examples
Example 1
Input
root = [1,2,3,4,5,null,7]
Output
[1,#,2,3,#,4,5,7,#]
Each level is threaded left-to-right with next pointers; # marks level ends.
Example 2
Input
root = []
Output
[]
Nothing to connect.