Trusted answers to developer questions

How to connect nodes at the same level in a binary tree

Free System Design Interview Course

Many candidates are rejected or down-leveled due to poor performance in their System Design Interview. Stand out in System Design Interviews and get hired in 2024 with this popular free course.

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
Copyright ©2024 Educative, Inc. All rights reserved
Did you find this helpful?