Populating Next Right Pointers in Each Node
Medium · Trees · Linked List · Tree · Depth-First Search · Breadth-First Search · Binary Tree
Problem
You are given a perfect binary tree: every node that is not a leaf has exactly two children, and all the leaves are on the same level. Each node has an extra pointer, next, which starts as None.
Set every next to the node immediately to its right on the same level — even when that node has a different parent. The last node of each level keeps next = None. Return the root.
The tests read your result the way LeetCode prints it: from the leftmost node of each level they follow next, list the values, and close the level with "#". The tree [1,2,3,4,5,6,7] should read [1,"#",2,3,"#",4,5,6,7,"#"].
Follow-up: use O(1) extra space — no queue, and no recursion.
The node type and three helpers are provided:
Examples
Input: root = [1,2,3,4,5,6,7] Output: [1,"#",2,3,"#",4,5,6,7,"#"]
2 points to 3, and 4 → 5 → 6 → 7. The link from 5 to 6 crosses from one parent to another. The last node of each level points to None, and each # marks the end of a level.
Input: root = [] Output: []
No nodes, nothing to connect.
Constraints
- 0 <= number of nodes <= 2^12 - 1
- -1000 <= Node.val <= 1000
- the tree is perfect: all leaves are on the same level and every other node has two children
Approaches
- Recursively link every neighbouring pair — time O(n^1.58), space O(log n)
Follow-up
Use only constant extra space. (LeetCode counts a recursion stack as free, but walking each level along the links already set needs no recursion at all.)
Related problems
Start free on Cariara · Coding problems · System design studio
