163. Connect every node of a binary tree to its next node on the same level (a `next` pointer).
MediumTrees
Technical
Show model answer
The easy method is a level-by-level BFS: within a level, set each dequeued node's `next` to the following node in that level, and the last node's to null. That is O(n) time and O(w) space.
For O(1) extra space, use the level already linked to link the one below it. Walk the current level through `next` pointers while building the next level's chain with a dummy head and a tail pointer: append each left and right child to the tail. Then move to the dummy's `next` and repeat. For a perfect tree it simplifies to `node.left.next = node.right` and `node.right.next = node.next?.left`.