Populating Next Right Pointers in Each Node II
Medium · Trees · Linked List · Tree · Depth-First Search · Breadth-First Search · Binary Tree
Problem
Each node of a binary tree has the fields val, left, right and next. This time the tree is arbitrary: children may be missing anywhere.
Set each node's next pointer to the nearest node to its right on the same level, or None if there is none. Every next starts as None. Return the root.
Aim for constant extra space. The tests read the result with to_next_list(root): each level from its leftmost node along the next pointers, followed by "#". For the first example that is [1,"#",2,3,"#",4,5,7,"#"].
The tree is given in level order, with None for a missing child. from_level([1,2,3,4,5,None,7]) builds it from Node objects and to_level(root) turns it back into a list.
Examples
Input: root = [1,2,3,4,5,None,7] Output: [1,"#",2,3,"#",4,5,7,"#"]
5 and 7 have different parents and a missing node between them, but they are still neighbours on their level.
Input: root = [1,2,None,3] Output: [1,"#",2,"#",3,"#"]
Every level has a single node, so every next stays None.
Input: root = [] Output: []
There are no nodes and nothing to link.
Constraints
- 0 <= number of nodes <= 6000
- -100 <= Node.val <= 100
Approaches
- Breadth-first, one level at a time — time O(n), space O(w)
Follow-up
With a perfect tree every node has both children or none, and node.right.next = node.next.left links across a gap directly. Why does that shortcut fail here, and what replaces it?
Related problems
Start free on Cariara · Coding problems · System design studio
