Populating Next Right Pointers in Each Node II

Populating Next Right Pointers in Each Node II - Problem

Given a binary tree with the following structure:

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

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note: This is the general case where the binary tree can be any binary tree (not necessarily a perfect binary tree).

Input & Output

Example 1 — Perfect Binary Tree

$ Input: root = [1,2,3,4,5,6,7]

› Output: [1,2,3,4,5,6,7]

💡 Note: Level 0: 1; Level 1: 2 → 3; Level 2: 4 → 5 → 6 → 7. Each node points to its next right node in the same level.

Example 2 — General Binary Tree

$ Input: root = [1,2,3,4,5,null,7]

› Output: [1,2,3,4,5,7]

💡 Note: Level 0: 1; Level 1: 2 → 3; Level 2: 4 → 5 → 7. Node 6 is missing, so 5 connects directly to 7.

Example 3 — Single Node

$ Input: root = [1]

› Output: [1]

💡 Note: Only one node exists, so no next pointers need to be set.

Constraints

The number of nodes in the tree is in the range [0, 6000]
-100 ≤ Node.val ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input

Binary tree [1,2,3,4,5,null,7] with null next pointers

Process

Connect nodes level by level: 2→3, then 4→5→7

Output

Same tree with all next pointers populated

Key Takeaway

🎯 Key Insight: Connect nodes level by level using the tree's natural structure - either with BFS or by leveraging already established connections

Asked in

M Microsoft 15 A Amazon 12 F Facebook 8 G Google 6

The key insight is to connect nodes level by level using either BFS or by utilizing already established next pointers from the previous level. The optimal approach uses constant space by leveraging existing connections to traverse levels without extra data structures. Time: O(n), Space: O(1) for optimal solution.

Common Approaches

Approach	Time	Space	Notes
✓ Level Order Traversal (BFS)	O(n)	O(w)	Use BFS to process nodes level by level and connect them
Constant Space Solution	O(n)	O(1)	Use already established next pointers to traverse levels without extra space

Level Order Traversal (BFS) — Algorithm Steps

Use a queue to perform level-order traversal
For each level, process all nodes and connect them
Set next pointers between consecutive nodes in the same level

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Queue

Start with root in queue

Process Level

Connect all nodes in current level

Add Children

Add next level nodes to queue

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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

struct Node* createNode(int val) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    node->next = NULL;
    return node;
}

struct Node* solution(struct Node* root) {
    if (!root) return root;
    
    // Use array as queue (simplified for basic cases)
    struct Node* queue[10000];
    int front = 0, rear = 0;
    
    queue[rear++] = root;
    
    while (front < rear) {
        int levelSize = rear - front;
        int levelStart = front;
        
        for (int i = 0; i < levelSize; i++) {
            struct Node* node = queue[front++];
            
            // Connect to next node in the same level
            if (i < levelSize - 1) {
                node->next = queue[front];
            }
            
            // Add children to queue for next level
            if (node->left) queue[rear++] = node->left;
            if (node->right) queue[rear++] = node->right;
        }
    }
    
    return root;
}

void printTreeArray(struct Node* root) {
    if (!root) {
        printf("[]\n");
        return;
    }
    
    struct Node* queue[10000];
    int front = 0, rear = 0;
    queue[rear++] = root;
    
    printf("[");
    int first = 1;
    
    while (front < rear) {
        struct Node* node = queue[front++];
        
        if (!first) printf(",");
        first = 0;
        
        if (node) {
            printf("%d", node->val);
            queue[rear++] = node->left;
            queue[rear++] = node->right;
        } else {
            printf("null");
        }
    }
    
    printf("]\n");
}

struct Node* buildSimpleTree() {
    // Build example tree [1,2,3,4,5,null,7]
    struct Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->right = createNode(7);
    return root;
}

int main() {
    // Simplified input parsing for basic test
    struct Node* root = buildSimpleTree();
    struct Node* result = solution(root);
    printTreeArray(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node exactly once during BFS traversal

✓ Linear Growth

Space Complexity

O(w)

Queue stores at most w nodes where w is maximum width of tree

✓ Linear Space

89.5K Views

Medium Frequency

~25 min Avg. Time

2.3K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Level Order Traversal (BFS) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler