Populate next pointers in a perfect binary tree
MicrosoftSoftware Engineer · Onsite
Last updated
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.
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.