LeetCode 117: Populating Next Right Pointers in Each Node II

Problem Restatement

We are given the root of a binary tree.

Each node has four fields:

val
left
right
next

We must populate every next pointer so that it points to the next node on the same level. If there is no node to the right, the next pointer should be None.

Unlike LeetCode 116, the tree is not necessarily perfect. Some nodes may have only one child or no children.

The official problem also asks us to use constant extra space, excluding recursive stack space. (leetcode.com)

For this tree:

        1
      /   \
     2     3
    / \     \
   4   5     7

After connecting:

        1 -> None
      /   \
     2  -> 3 -> None
    / \     \
   4 ->5 -> 7 -> None

Input and Output

Item	Meaning
Input	`root`, the root of a binary tree
Output	The same root node after modifying `next` pointers
Tree type	General binary tree
Next pointer	Points to the next node on the same level
Rightmost node	Points to `None`
Empty tree	Return `None`

LeetCode gives this node class:

class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next

The function shape is:

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        ...

Examples

Consider:

        1
      /   \
     2     3
    / \     \
   4   5     7

At level 0:

1 -> None

At level 1:

2 -> 3 -> None

At level 2:

4 -> 5 -> 7 -> None

Notice that node 5 connects to node 7 even though they do not share the same parent.

For an empty tree:

root = None

the answer is:

None

First Thought: Use Breadth-First Search

A direct solution is BFS.

For each level:

Store nodes in a queue.
Connect adjacent nodes in the queue.

That works correctly.

But the follow-up asks for constant extra space.

So instead of a queue, we should use the already-built next pointers to move horizontally across levels.

Key Insight

While processing one level, we can build the next pointers for the next level.

We maintain three pointers:

Pointer	Meaning
`cur`	Current node on the current level
`head`	First node of the next level
`tail`	Last connected node on the next level

As we scan the current level using cur.next:

If cur.left exists, append it to the next-level chain.
If cur.right exists, append it to the next-level chain.

This creates the next level from left to right.

Then we move down:

cur = head

and repeat.

Algorithm

Initialize:

cur = root

While cur is not None:

Create:
1. head = None
2. tail = None
Walk across the current level using cur.next.
For each child:
1. If this is the first child, set head.
2. Otherwise, connect tail.next.
3. Move tail.
After finishing the level:
1. Move to the next level with cur = head.

Return root.

Correctness

At the start of each outer loop iteration, cur points to the first node of the current level, and all next pointers on that level are already correct.

The inner loop traverses the entire current level using cur.next. For every node, the algorithm processes its children from left to right.

When a child is found:

If it is the first child discovered on the next level, it becomes head.
Otherwise, it is connected after tail.

Thus, children are connected in exact left-to-right order across the next level.

After processing all nodes on the current level, the next level has a complete linked structure through next pointers. The algorithm then moves to head, which is the first node of the next level.

By repeating this process level by level, all nodes receive the correct next pointers. Nodes at the right edge naturally keep next = None because no later node is connected after them.

Therefore, the final tree satisfies the required next-pointer structure.

Complexity

Metric	Value	Why
Time	`O(n)`	Every node is visited once
Space	`O(1)`	Only a few pointers are used

Here, n is the number of nodes.

The algorithm uses no queue and no auxiliary data structure proportional to tree size.

Implementation

from typing import Optional

# Definition for a Node.
# class Node:
#     def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
#         self.val = val
#         self.left = left
#         self.right = right
#         self.next = next

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        cur = root

        while cur is not None:
            head = None
            tail = None

            while cur is not None:
                for child in [cur.left, cur.right]:
                    if child is None:
                        continue

                    if head is None:
                        head = child
                        tail = child
                    else:
                        tail.next = child
                        tail = child

                cur = cur.next

            cur = head

        return root

Code Explanation

Start from the root level:

cur = root

The outer loop processes one level at a time:

while cur is not None:

head stores the first node of the next level:

head = None

tail stores the last connected node:

tail = None

Traverse the current level using already-built next pointers:

while cur is not None:

Process both children:

for child in [cur.left, cur.right]:

Skip missing children:

if child is None:
    continue

If this is the first child on the next level:

if head is None:
    head = child
    tail = child

Otherwise, append the child:

tail.next = child
tail = child

Move horizontally across the current level:

cur = cur.next

After the current level is finished, move downward:

cur = head

Finally:

return root

Testing

from typing import Optional

class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next

class Solution:
    def connect(self, root: Optional[Node]) -> Optional[Node]:
        cur = root

        while cur is not None:
            head = None
            tail = None

            while cur is not None:
                for child in [cur.left, cur.right]:
                    if child is None:
                        continue

                    if head is None:
                        head = child
                        tail = child
                    else:
                        tail.next = child
                        tail = child

                cur = cur.next

            cur = head

        return root

def levels_by_next(root):
    ans = []
    leftmost = root

    while leftmost is not None:
        level = []
        cur = leftmost
        next_leftmost = None

        while cur is not None:
            level.append(cur.val)

            if next_leftmost is None:
                if cur.left is not None:
                    next_leftmost = cur.left
                elif cur.right is not None:
                    next_leftmost = cur.right

            cur = cur.next

        ans.append(level)
        leftmost = next_leftmost

    return ans

def run_tests():
    s = Solution()

    root1 = Node(
        1,
        Node(2, Node(4), Node(5)),
        Node(3, None, Node(7)),
    )

    s.connect(root1)

    assert levels_by_next(root1) == [
        [1],
        [2, 3],
        [4, 5, 7],
    ]

    root2 = Node(1)

    s.connect(root2)

    assert levels_by_next(root2) == [[1]]

    root3 = None

    assert s.connect(root3) is None

    root4 = Node(
        1,
        Node(2, None, Node(5)),
        Node(3),
    )

    s.connect(root4)

    assert levels_by_next(root4) == [
        [1],
        [2, 3],
        [5],
    ]

    print("all tests passed")

run_tests()

Test meaning:

Test	Why
Sparse tree example	Confirms cross-parent connections
Single node	Minimum non-empty tree
Empty tree	Confirms base case
Missing left child	Confirms general binary tree handling