⚡Flashcard Drill➔
NeetCode #417LC-116MediumTrees
← Back to All Problems

#417 · #116 · Populating Next Right Pointers in Each Node(填充每个节点的下一个右侧节点指针)

📌 Problem Statement & Constraints

You are given a perfect binary tree where all leaves are at the same depth and every parent has two children. Each node has an extra next pointer; populate it so each node points to the next node on the same level, with the last node of each level pointing to None. Constraints: the number of nodes is in [0, 2^12 - 1].

💡 Core Algorithmic Approaches

  1. Process the tree level by level using the next pointers themselves -- no queue is needed, so the extra space is O(1).
  2. For each level, walk the chain of parents and connect: left.next = right, and right.next = parent.next.left when the parent has a next.
  3. The second connection is the crucial one: it links across different parents on the same level.
  4. Then descend via leftmost = leftmost.left.

💻 Benchmark Python3 Implementation

class Solution:
    def connect(self, root: "Optional[Node]") -> "Optional[Node]":
        if not root:
            return None
        leftmost = root
        while leftmost.left:               # while there is a level below
            head = leftmost
            while head:
                # connect the two children of this parent
                head.left.next = head.right
                # connect across parents on the same level
                if head.next:
                    head.right.next = head.next.left
                head = head.next           # move along the current level
            leftmost = leftmost.left       # descend one level
        return root

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each node is visited once.
💾 Space Complexity
O(1) extra: the level chain is traversed through the next pointers.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting the cross-parent connection: without head.right.next = head.next.left, the levels would break between subtrees.
  • Using a BFS queue: it works but costs O(n) space, while the pointer-based traversal needs O(1).
  • Connecting head.right.next = head.next: that links to a node on the same level but the wrong one; the target is head.next.left.
  • Looping while head without descending: the traversal would never reach the lower levels.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Trees Problems