Populate Next Right Pointers 🎯

Welcome to the Populate Next Right Pointers lesson! In this tutorial, we will learn about the concept of populating the next right pointers in a complete binary tree. This technique is used in various data structures and algorithms, making it an essential skill for any developer. 📝

What is a Complete Binary Tree? 📝

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. Let's visualize a complete binary tree with the help of an example:

In a complete binary tree, the number of nodes at each level increases from left to right, starting from 1. This tree has 8 nodes, and the next right pointer helps to navigate through the tree efficiently. 💡

Understanding Next Right Pointers 💡

The idea behind populating the next right pointers is to make the tree more accessible by creating a connection between the nodes at the same level of different branches. To do this, we will assign the next right pointer for the rightmost node in a level to the leftmost node in the next level. This way, we can traverse the tree by following the next right pointers, which simplifies the traversal process.

Let's modify the previous example and add next right pointers to the tree:

1 -> null
/   \
2 -> 4
/ \   \
4 -> null 5 -> 6
/
7 -> null

As you can see, the rightmost node at level 1 (node 2) has a next right pointer pointing to the leftmost node at level 2 (node 4). Similarly, the rightmost node at level 2 (node 5) has a next right pointer pointing to the leftmost node at level 3 (node 7).

Implementing Next Right Pointers 💡

Now that we have a good understanding of the concept, let's implement the next right pointers in a complete binary tree. We will write two examples, one in C++ and another in Python, to demonstrate the implementation.

C++ Example 💡

cpp

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node* nextRight;

    Node(int data) {
        this->data = data;
        this->left = nullptr;
        this->right = nullptr;
        this->nextRight = nullptr;
    }
};

void connect(Node* root) {
    if (!root) return;

    if (!root->left && !root->right) return;

    if (root->right) connect(root->right);

    root->nextRight = (root->right ? root->right->nextRight : root->left);

    if (root->left) connect(root->left);
}

void printNextRight(Node* root) {
    if (!root) return;

    if (root->nextRight) cout << root->data << " -> " << (root->nextRight ? root->nextRight->data : -1) << endl;

    if (root->left) printNextRight(root->left);
    if (root->right) printNextRight(root->right);
}

int main() {
    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);
    printNextRight(root);

    return 0;
}

Output:

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

Python Example 💡

python

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.next_right = None

def connect(root):
    if not root:
        return

    if not root.left and not root.right:
        return

    if root.right:
        connect(root.right)

    root.next_right = (root.right and root.right.next_right) or root.left

    if root.left:
        connect(root.left)

def print_next_right(root):
    if not root:
        return

    if root.next_right:
        print(f"{root.data} -> {root.next_right.data}")

    if root.left:
        print_next_right(root.left)
    if root.right:
        print_next_right(root.right)

def main():
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)
    root.right.left = Node(6)
    root.right.right = Node(7)

    connect(root)
    print_next_right(root)

if __name__ == "__main__":
    main()

Output:

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

Quiz 🎯

Congratulations on completing the Populate Next Right Pointers lesson! With this knowledge, you are well-equipped to tackle various data structures and algorithms. Keep practicing and learning! 🎉