Populating Next Right Pointers in Each Node II

Medium#117tree nodes

Every node of a binary tree has one more pointer, next, which starts as none. Point each node's next at the node to its right on the same level; the rightmost node of a level keeps none. The tree need not be full, so a level may have gaps. Return the root. Our example: the tree [6, 2, 9, 1, 4, none, 8] in level order — after the run the levels read 6 → none; 2 → 9 → none; 1 → 4 → 8 → none.

117 Populating Next Right Pointers in Each Node IIWalkthrough · 1×

Example: link each node of [6, 2, 9, 1, 4, none, 8] to its right neighbour on the level.

629148queuefront on the left—
not reachedwaiting in the queuecurrentdone

The tree is not empty

01/48
restart · back · play · step
Speed
1function connect(root):
2 if root is none:
3 return none
4 queue = [root]
5 while queue is not empty:
6 size = queue.size
7 for i from 1 to size:
8 node = queue.popFront()
9 if i < size:
10 node.next = queue.front
11 if node.left is not none:
12 queue.pushBack(node.left)
13 if node.right is not none:
14 queue.pushBack(node.right)
15 return root
state
queue
–
size
–
i
–
node
–
node.next
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. The queue holds the nodes in level order: the children go to the back, behind every node of the level still waiting.
  2. So while i < size, the front of the queue is the next node on the same level, whichever parent it hangs from.
  3. The last node of a level (i = size) sees the next level at the front, so its next is left as none.

Complexity

Time O(n): each node enters and leaves the queue once. Memory O(w): the queue holds at most about two levels, w is the widest level.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.