DSA · Trees · #138
Populating Next Right Pointers in Each Node II
Module 44 · difficulty 3/5·⏱ 30:00starts on first keystroke
Given a binary tree where each node has `val`, `left`, `right`, and a `next` pointer, populate each `next` pointer to point to the node immediately to its right on the same level. If there is no such node, `next` should be set to `null`. Initially every `next` pointer is `null`. The tree is **not** guaranteed to be perfect — nodes may have zero, one, or two children. Implement `connect(root)`. It mutates the tree in place and returns `root`.
Examples
root = [1,2,3,4,5,null,7]→[1,#,2,3,#,4,5,7,#]— Level order with '#' marking the end of each level after next pointers are set: 1 -> null; 2 -> 3 -> null; 4 -> 5 -> 7 -> null.root = []→[]— An empty tree returns null; nothing to connect.root = [1,2,null,4]→[1,#,2,#,4,#]— Skewed/sparse tree: each level has a single node, so every next stays null.
Constraints
- · The number of nodes is in the range [0, 6000].
- · -100 <= Node.val <= 100
- · The tree may be any shape (not necessarily perfect).
- · All next pointers start as null.
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.