Populating Next Right Pointers in Each Node - CPP Solution

1. Introduction

In this blog post, we discuss a problem involving the connection of nodes in a perfect binary tree. The goal is to populate each next pointer in the tree to point to its next right node, enhancing the tree's traversal efficiency.

Problem

Given a perfect binary tree (where all leaves are on the same level, and every parent has two children), the task is to populate each node's next pointer to point to its next right node. If a node does not have a next right node, its next pointer should be set to NULL.

2. Solution Steps

1. Traverse the tree level by level.

2. Connect each node’s next pointer to the node on its right.

3. For the rightmost node on each level, set the next pointer to NULL.

4. Repeat the process for all levels of the tree.

3. Code Program

#include <iostream>
using namespace std;

// Node structure definition
struct Node {
    int val;
    Node *left, *right, *next;
    Node(int x) : val(x), left(nullptr), right(nullptr), next(nullptr) {}
};

// Function to connect the next right pointers
void connect(Node* root) {
    if (!root) return;

    Node* levelStart = root;
    while (levelStart->left) {
        Node* current = levelStart;
        while (current) {
            current->left->next = current->right;
            if (current->next) {
                current->right->next = current->next->left;
            }
            current = current->next;
        }
        levelStart = levelStart->left;
    }
}

// Function to print the next pointers of each node
void printNextPointers(Node* root) {
    Node* current = root;
    while (current) {
        Node* temp = current;
        while (temp) {
            cout << temp->val << " -> ";
            temp = temp->next;
        }
        cout << "NULL\n";
        current = current->left;
    }
}

int main() {
    // Creating a perfect binary tree
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);

    connect(root);
    printNextPointers(root); // Expected output: Connection of next pointers in each level
    return 0;
}

Output:

1 -> NULL
2 -> 3 -> NULL
4 -> 5 -> 6 -> 7 -> NULL

Explanation:

The connect function populates the next pointers in each node of a perfect binary tree. 

Starting from the root, it traverses level by level. For each node, it sets the next pointer of its left child to its right child. For the right child, the next pointer is set to the left child of the node's next sibling, if available. This ensures that all nodes on the same level are connected in a rightward manner. 

The printNextPointers function helps in demonstrating the structure of the updated tree, showing the connections formed by the next pointers.