Coding questions · Microsoft

Populate next pointers in a perfect binary tree

Evaluates proficiency in tree traversal and in-place pointer manipulation, emphasizing the perfect binary tree invariant and space-time trade-offs; category/domain: Coding & Algorithms. It is commonly asked because it tests ability to perform level-wise linking under an O(1) extra-space constraint and operates at the implementation-level of algorithms and data structures.

You are given a perfect binary tree (all leaves at the same level; every internal node has two children). Each node has fields left, right, and next.

Set each node’s next pointer to its immediate neighbor on the right within the same level. If there is no neighbor, set next = null.

Do this with O(1) extra space (not counting recursion stack) and return the root.

Populate Next Pointers in a Perfect Binary Tree

For a perfect tree represented in level order, return each node's next value or None in level-order position.

Constraints

level_order represents a perfect binary tree

Examples

Example 1

Input: ([1, 2, 3, 4, 5, 6, 7],)
Output: [None, 3, None, 5, 6, 7, None]

Explanation: Three-level perfect tree.

Example 2

Input: ([1],)
Output: [None]

Explanation: Root has no neighbor.

Hints

Within each level, every node points to the next array position except the last.