#117 Populating Next Right Pointers in Each Node II

frequently reported atBloomberg Meta Microsoft Amazon Google

the problem

In plain words

Every node has an extra pointer next. Point it at the node immediately to its right on the same level, or null if it's the last node of its level. The tree can have any shape (not necessarily perfect). Return the root. The node class is Node { int val; Node left, right, next; }.

in root = [1,2,3,4,5,null,7]

out [1,#,2,3,#,4,5,7,#]

Each level read through the next pointers; # ends a level. 5's next is 7, across the gap under 3.

in root = []

out []

0 ≤ number of nodes ≤ 6000
-100 ≤ Node.val ≤ 100
Follow-up: use only O(1) extra space (the recursion stack doesn't count)

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternTree BFS (level order)In-place linked-list rewiring

Level order already visits each level left to right — link every node to the one polled after it. For O(1) space: once level d is linked, it is a linked list. Walk it with next and build level d + 1's links behind a dummy head.

solutions

From brute force to optimal

Size-snapshot BFS; keep prev within a level and set prev.next = node.

Offer root.
Per level: prev = null; poll size nodes.
If prev != null, prev.next = node; prev = node.
Offer children.

timeO(n)

Each node polled once.

spaceO(w)

The queue holds a whole level — the follow-up wants better.

javajava.util.*

1class Solution {2    public Node connect(Node root) {3        if (root == null) return null;4        Deque<Node> queue = new ArrayDeque<>();5        queue.offer(root);6        while (!queue.isEmpty()) {7            int size = queue.size();8            Node prev = null;                         // left neighbour on this level9            for (int i = 0; i < size; i++) {10                Node node = queue.poll();11                if (prev != null) prev.next = node;   // link neighbour → me12                prev = node;13                if (node.left != null) queue.offer(node.left);14                if (node.right != null) queue.offer(node.right);15            }16            // the last node of each level keeps next == null17        }18        return root;19    }20}

Treat the current level as a linked list (via next). While walking it, append each child to a tail pointer that starts at a dummy node — that links the next level.

head = root; dummy = new Node(0).
While head != null: dummy.next = null; tail = dummy.
For cur = head; cur != null; cur = cur.next: append cur.left, then cur.right, to tail.
head = dummy.next (the first node of the next level).

timeO(n)

Each node is visited once as cur and linked once as a child.

spaceO(1)

One dummy node and two pointers, whatever the size of the tree.

javajava.util.*

1class Solution {2    public Node connect(Node root) {3        Node dummy = new Node(0);                     // sits in front of the next level4        Node head = root;                             // first node of the level we are walking5        while (head != null) {6            dummy.next = null;7            Node tail = dummy;                        // last node linked on the next level so far8            for (Node cur = head; cur != null; cur = cur.next) {   // walk this level by its next links9                if (cur.left != null) { tail.next = cur.left; tail = tail.next; }10                if (cur.right != null) { tail.next = cur.right; tail = tail.next; }11            }12            head = dummy.next;                        // the next level is now a linked list13        }14        return root;15    }16}

in the room

How to say it in the interview

talk track

Start with BFS: link prev → node inside each level.
Then: "the follow-up asks for O(1) space — but after I link a level, it's already a linked list, so I can walk it without a queue."
Draw the dummy + tail trick on example 1; it's the same dummy-head idea as merging linked lists.

traps

Linking the last node of a level to the first node of the next level — reset prev (or the dummy) for every level.
Assuming a perfect tree (that's LC 116): cur.left.next = cur.right breaks when children are missing.
Not clearing dummy.next before each level: the old level's first node sneaks back in and the loop never ends.

what they ask next

Follow-ups

Perfect binary tree (LC 116)?

Simpler: cur.left.next = cur.right, and cur.right.next = cur.next.left when cur.next exists. Still O(1) space.

Recursive O(1) version?

Possible, but you must link the right subtree before the left one, because a left child may need a next pointer found far to the right. The iterative level walk is easier to get right.

before you submit

Edge cases to test

Empty tree → return null.
Gaps: in [1,2,3,4,null,null,5], node 4's next is 5 — across two missing children.
A level with a single node: its next stays null.

practise next