Full lesson preview

Populate next right pointers

Connect each node's next pointer to its immediate right neighbor in a perfect binary tree (constant extra space).

Python practice30 minTrees & Binary TreesAdvancedLast updated March 29, 2026

Problem statement

You are given the root of a perfect binary tree (all leaves are at the same level, and every parent has two children). Each node has an extra pointer called next that should be set to point to its immediate right neighbor on the same level. If there is no neighbor, next should be set to None. Implement the function connect(root) that populates each next pointer. Your algorithm should run in O(n) time and use O(1) extra space (excluding recursion/stack space). Return the root after populating next pointers. Note: For testing and visualization we provide helper utilities to build a tree from a level-order list and to serialize the resulting next-pointer structure as a list of lists, where each inner list contains node values for one level following next pointers from left to right.

Task

Given a perfect binary tree, set each node's next pointer to the node on its right at the same level (or None). Return the root after connections.

Examples

Example: small perfect tree

Input

connect(build([1,2,3,4,5,6,7])) then get_values_by_next(root)

Output

[[1], [2, 3], [4, 5, 6, 7]]

After connecting, level 0: 1 -> None; level 1: 2 -> 3 -> None; level 2: 4 -> 5 -> 6 -> 7 -> None. The serializer returns lists per level following next pointers.

Input format

A function call: connect(root) where root is built via build(level_order_list). Tests call connect(build([...])) and then get_values_by_next(...) to inspect next pointers.

Output format

The function returns the root with next pointers correctly populated. Tests will serialize the next-pointer links into a list of lists and compare its string representation.

Constraints

- The tree is perfect: every non-leaf node has exactly two children and all leaves are at the same depth. - Node values are integers. - 0 <= number of nodes <= 2^12 (practical limit for tests). - Expected time O(n) and O(1) extra space (iterative level-by-level using next pointers).

Samples

Sample 1

Input

[1,2,3,4,5,6,7]

Output

[[1], [2, 3], [4, 5, 6, 7]]

Standard perfect tree of height 3; next pointers connect siblings and across parents.