Trusted answers to developer questions

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)

**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 Â©2022 Educative, Inc. All rights reserved

RELATED COURSES

View all Courses

Keep Exploring

Related Courses