Code Implementation

class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next

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

class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;
    Node() : val(0), left(nullptr), right(nullptr), next(nullptr) {}
    Node(int _val) : val(_val), left(nullptr), right(nullptr), next(nullptr) {}
    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};

class Solution {
public:
    Node* connect(Node* root) {
        Node* curr = root;
        while (curr) {
            Node dummy(0);
            Node* tail = &dummy;
            while (curr) {
                if (curr->left) {
                    tail->next = curr->left;
                    tail = tail->next;
                }
                if (curr->right) {
                    tail->next = curr->right;
                    tail = tail->next;
                }
                curr = curr->next;
            }
            curr = dummy.next;
        }
        return root;
    }
};
      

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;
    public Node() {}
    public Node(int val) { this.val = val; }
    public Node(int val, Node left, Node right, Node next) {
        this.val = val;
        this.left = left;
        this.right = right;
        this.next = next;
    }
}

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

function Node(val, left, right, next) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
    this.next = next === undefined ? null : next;
}

var connect = function(root) {
    let curr = root;
    while (curr) {
        let dummy = new Node(0);
        let tail = dummy;
        while (curr) {
            if (curr.left) {
                tail.next = curr.left;
                tail = tail.next;
            }
            if (curr.right) {
                tail.next = curr.right;
                tail = tail.next;
            }
            curr = curr.next;
        }
        curr = dummy.next;
    }
    return root;
};
      

Problem Description

You are given a binary tree where each node contains a next pointer, which should point to its next right node on the same level. If there is no next right node, the next pointer should be set to null.

Unlike the simpler version of this problem, the binary tree is not necessarily perfect or complete—some nodes may be missing children. Your task is to fill in each node's next pointer so that it points to its next right node at the same level, or null if there is none.

• Each node may have zero, one, or two children.
• You must connect the next pointers in-place, without using extra space for data structures (apart from a few pointers/variables).
• There is only one valid solution for each input tree.

Thought Process

The first idea might be to use a level-order traversal (BFS) with a queue, connecting nodes as we go. This works well for a perfect binary tree or when we are allowed extra space, but the problem asks for an in-place solution with O(1) extra space (excluding recursion stack).

We need to connect each node's next pointer to its right neighbor without using additional data structures. In a perfect tree, we could always connect left->next = right and right->next = parent.next.left. However, since this tree may be incomplete, we can't rely on children always being present.

This suggests a more careful traversal: as we process each level, we need to build the next pointers for the next level as we go, using only the pointers already established.

Solution Approach

• Use a dummy node: At each level, we use a temporary dummy node to start the next chain for the next level. This helps us easily build the chain without worrying about special cases for the first node.
• Iterate level by level: For each node at the current level, connect its children (if any) to the next chain for the next level. Move through the current level using the next pointers we've already established.
• Advance to next level: After finishing one level, move to the start of the next level (which is dummy.next).
• Repeat: Continue this process until there are no more levels to process.

This approach is efficient because:

• We never use extra memory proportional to the size of the tree—just a few pointers.
• We traverse each node exactly once.

Example Walkthrough

Consider the following binary tree:

        1
      /   \
     2     3
      \     \
       5     7
  

• Start at level 1: Node 1. Its children are 2 and 3. So 2's next is 3, and 3's next is null.
• Move to level 2: Nodes 2 and 3. 2 has a right child 5, 3 has a right child 7. So 5's next is 7, and 7's next is null.
• Move to level 3: Nodes 5 and 7. Both are leaves, so nothing to connect.

The final structure has next pointers set as follows:

• 1's next = null
• 2's next = 3
• 3's next = null
• 5's next = 7
• 7's next = null

Time and Space Complexity

• Brute-force (using a queue): Time complexity is O(N) since each node is visited once. Space complexity is O(N) due to the queue storing nodes at each level.
• Optimized in-place solution: Time complexity remains O(N), as each node is visited once. Space complexity is O(1), since only a few pointers (dummy and tail) are used at any time, regardless of tree size.

The optimized solution is preferable because it meets the problem's in-place constraint and is efficient both in time and space.

Summary

To solve "Populating Next Right Pointers in Each Node II," we iteratively traverse each level of the binary tree, using a dummy node and tail pointer to build the next chain for the next level. This approach requires no extra memory beyond a few pointers, is straightforward to implement, and efficiently connects all nodes' next pointers even when the tree is irregular or incomplete. The key insight is to use already established next pointers to traverse levels and a dummy node to simplify connecting the next level.