Problem #117: Populating Next Right Pointers in Each Node II

Intuition & Strategy Breakdown

Use BFS level order traversal or level pointers. Connect node.left -> node.right and node.right -> next available child in parent's next chain.

Python Solution

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root: return None
        curr = root
        while curr:
            dummy = Node(0)
            prev = dummy
            while curr:
                if curr.left:
                    prev.next = curr.left
                    prev = prev.next
                if curr.right:
                    prev.next = curr.right
                    prev = prev.next
                curr = curr.next
            curr = dummy.next
        return root

Java Solution

class Solution {
    public Node connect(Node root) {
        if (root == null) return null;
        Node curr = root;
        while (curr != null) {
            Node dummy = new Node(0);
            Node prev = dummy;
            while (curr != null) {
                if (curr.left != null) {
                    prev.next = curr.left;
                    prev = prev.next;
                }
                if (curr.right != null) {
                    prev.next = curr.right;
                    prev = prev.next;
                }
                curr = curr.next;
            }
            curr = dummy.next;
        }
        return root;
    }
}