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.