Related Tags

binary tree
data structures

# How to connect nodes at the same level in a binary tree Educative Answers Team

Connecting all the nodes at the same level of a binary tree involves linking the right_neighbor pointer of each node (in a tree) to its adjacent node on the same level.

A binary tree (LEFT) and a binary tree with all nodes connected at the same level (RIGHT)

## Implementation

Level-Order traversal refers to visiting all the nodes at the same level before iterating to the next level. In the following code, a level order traversal is done on the tree, and the right_neighbor is set to the immediate neighbor on the same level.

#include <iostream>
using namespace std;
#include <queue>
// A tree node
struct Tree
{
char data;
Tree *left;
Tree *right;
Tree *right_neighbor;
Tree(char data)
{
this -> data = data;
left = NULL;
right = NULL;
right_neighbor = NULL;
}
};
// Function to print the right_neighbor of the nodes
void PreOrderTraversal(Tree *node)
{
if(node == NULL){
return;
}
else{
if(node -> right_neighbor != NULL){
cout << node -> data << "-> " << node -> right_neighbor -> data << endl;
}
else{
cout << node -> data << "-> NULL" << endl;
}
PreOrderTraversal(node -> left);
PreOrderTraversal(node -> right);
}
}
int main() {
// The tree
Tree *root = new Tree('a');
root -> left = new Tree('b');
root -> right = new Tree('c');
root -> left -> left = new Tree('d');
root -> left -> right = new Tree('e');
queue <Tree*> Q;
// Enqueue the root node
Q.push(root);
// Enqueue NULL to serve a partition between levels
Q.push(NULL);
while (!Q.empty()){
// Dequeue the element from the front of the queue
Tree *node = Q.front();
Q.pop();
if(node == NULL){
// This shows that a level has finished, so enqueue
// NULL to denote that.
if(!Q.empty()){
Q.push(NULL);
}
}
else{
// Peek at the element at the front of the queue and
// set the right pointer to the adjacent element in the queue
node -> right_neighbor = Q.front();
// Enqueue its left and right children if they exist
if(node -> left != NULL){
Q.push(node -> left);
}
if(node -> right != NULL){
Q.push(node -> right);
}
}
}
PreOrderTraversal(root);
return 0;
}

RELATED TAGS

binary tree
data structures 