Populate next pointers in a perfect binary tree
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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.
Quick Answer: 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.
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
Input: ([1, 2, 3, 4, 5, 6, 7],)
Expected Output: [None, 3, None, 5, 6, 7, None]
Explanation: Three-level perfect tree.
Input: ([1],)
Expected Output: [None]
Explanation: Root has no neighbor.
Input: ([],)
Expected Output: []
Explanation: Empty tree.
Hints
- Within each level, every node points to the next array position except the last.