Populating Next Right Pointers in Each Node (LeetCode 116)

The problem

You get a perfect binary tree: every internal node has exactly two children and all leaves are on the same level. Each node has an extra pointer next, initially None. Set every next to the node immediately to its right on the same level, or leave it None if it’s the last node on its level. Return the root.

Input:          1
              /   \
             2     3
            / \   / \
           4   5 6   7

Output (next pointers by level):
1 -> None
2 -> 3 -> None
4 -> 5 -> 6 -> 7 -> None

Each level becomes a small linked list, left to right.

How to think about it

Start with the obvious BFS. Run a level-order traversal; within each level, point every node at the next one you pop, and the last at None. That is O(n) time and clearly correct, but the queue holds a whole level, which is O(n) space for a perfect tree. The follow-up asks for constant extra space.

The key insight: once a level is linked, it is a queue. After you’ve wired level d with next pointers, you can walk it left to right with head = head.next, without any deque. And while you’re walking level d, you have everything you need to wire level d + 1:

• Inside one parent: head.left.next = head.right.
• Across two parents: head.right.next = head.next.left, when head.next exists.

Walk level by level from the leftmost node. leftmost starts at the root. For each level, walk across it with head, wiring the children. Then move down with leftmost = leftmost.left. Stop when leftmost has no children, since that is the last level. The perfect-tree guarantee means every non-leaf has both children, so no None checks are needed on them.

Which pattern is this? Tree BFS, level by level, with the tree’s own pointers replacing the queue. The tell is “connect nodes on the same level” plus “O(1) extra space”.

Approach

1. If root is None, return None.
2. Set leftmost = root.
3. While leftmost.left exists (the level below is not empty):
   • head = leftmost; while head exists:
     • head.left.next = head.right,
     • if head.next exists, head.right.next = head.next.left,
     • head = head.next;
   • leftmost = leftmost.left.
4. Return root.

Solution

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

def connect(root):
    if not root: return None
    leftmost = root
    while leftmost.left:                          # a level below exists
        head = leftmost                           # walk this level using its next links
        while head:
            head.left.next = head.right           # siblings under the same parent
            if head.next: head.right.next = head.next.left   # across neighbouring parents
            head = head.next
        leftmost = leftmost.left                  # go down one level
    return root
# after connect: root.left.next -> root.right, and across cousins via parents' next

Dry run

On the 7-node tree above:

Reading the next chains afterwards: [1], [2, 3], [4, 5, 6, 7], each ending in None.

Complexity

• Time: O(n). Each node is visited once as head (except the leaves, which only get wired).
• Space: O(1). Just leftmost and head. No queue, no recursion.

Edge cases and pitfalls

• Empty tree: returns None.
• Single node: root.left is None, the loop never runs, and root.next stays None.
• Last node on each level: its next stays None because head.next is None for the rightmost parent, so head.right.next is never set.
• Not perfect? That’s LeetCode 117. Children can be missing, so you can’t assume head.left/head.right exist; build the next level with a dummy node and a tail pointer instead.
• Using the queue version when asked for O(1) space. It’s correct but misses the follow-up.

Related problems

• Binary Tree Right Side View (LeetCode 199): the node whose next stays None on each level is exactly what you see from the right.
• Binary Tree Level Order Traversal (LeetCode 102): the queue-based level walk this replaces.
• Merge Two Sorted Lists (LeetCode 21): the dummy-plus-tail trick you’d use for the non-perfect version.