Back to solutions

Populating Next Right Pointers in Each Node

MediumBinary Trees

In a perfect binary tree, set each node's next pointer to the node to its right on the same level, or null.

Open problem
Constraints
  • 0 <= nodes <= 2^12 - 1
  • The tree is perfect

Level links using established next pointers

Time O(n)Space O(1)

Process the tree level by level using the next pointers already set on the current level to traverse it, wiring the children's next pointers as you go. Uses no queue.

struct Node { int val; Node* left; Node* right; Node* next; };

Node* connect(Node* root) {
    Node* leftmost = root;
    while (leftmost && leftmost->left) {
        Node* head = leftmost;
        while (head) {
            head->left->next = head->right;
            if (head->next) head->right->next = head->next->left;
            head = head->next;
        }
        leftmost = leftmost->left;
    }
    return root;
}