How to Print Data in Binary Tree Level by Level in C++
- Write an Algorithm Using Queue to Print Data in Binary Tree Level by Level in C++
- Use Linked List Node to Print Data in Binary Tree Level by Level in C++
- Use Hashing Technique to Print Data in Binary Tree Level by Level in C++
The binary tree level-by-level traversal is known as Breadth-first traversal. This tutorial will teach you how to print data in a binary tree level-by-level in C++ and familiarize you with different methods to perform this task.
Using a queue is the proper way to print data in a binary tree level by level as a stack is for depth-first traversal. However, there’re three different ways to achieve this goal: writing your own algorithm using a queue (or linked list node) or using the Hashing technique.
Write an Algorithm Using Queue to Print Data in Binary Tree Level by Level in C++
In C++, you can use the features of the queue by including #include<queue> to write an algorithm that prints out data in a binary tree level by level in sorted order. As the queue follows FIFO (First-In-First-Out principle), you should initialize a queue and push the root to it.
Write a logical algorithm and apply it to the input binary tree, and you can use the null node (to separate the nodes by a newline). Remember, your interaction with a null node means no un-visited node has remained on the current level, and you can print a newline.
At the end of each binary tree level, there should be a null node representing its end. Initializing a queue to store data of type nodes, pushing root to it, and finally pushing the null node to the queue can insert a null node to a level.
#include <iostream>
#include <queue>
using namespace std;
class binT_node {
public:
int nodeData;
// declare left and right nodes of the binary tree
binT_node* left;
binT_node* right;
binT_node(int data, binT_node* lef, binT_node* rig) {
nodeData = data;
left = lef;
right = rig;
}
};
void print_dataT(binT_node* root) {
queue<binT_node*> que;
que.push(root);
while (true) {
int orderLength = que.size();
if (orderLength == 0) {
break;
}
int i = 0;
while (i < orderLength) {
binT_node* nod = que.front();
cout << (nod->nodeData) << " ";
if (nod->left != NULL) {
que.push(nod->left);
}
if (nod->right != NULL) {
que.push(nod->right);
}
que.pop();
i++;
}
cout << endl;
}
}
int main() {
binT_node* rootNode;
rootNode = new binT_node(1, NULL, NULL);
rootNode->left = new binT_node(2, NULL, NULL);
rootNode->right = new binT_node(3, NULL, NULL);
rootNode->left->left = new binT_node(4, NULL, NULL);
rootNode->left->right = new binT_node(5, NULL, NULL);
rootNode->right->left = new binT_node(6, NULL, NULL);
rootNode->right->right = new binT_node(7, NULL, NULL);
print_dataT(rootNode);
return 0;
}
Output:
1
2 3
4 5 6 7
It’s possible to print nodes at the same level in one iteration instead of printing one node on each iteration, and it’s another well-known approach to writing similar algorithms in C++.
This approach is a bit similar to the first one, including initializing the queue and pushing the root and null nodes to it.
Furthermore, if the temp is not null, print the value of node temp, push temp.left to queue if it’s not null, and push temp.right to queue if it’s not null, repeat the steps until the queue is empty.
Use Linked List Node to Print Data in Binary Tree Level by Level in C++
Visiting a node to put its child nodes in a FIFO queue is a standard approach because you can also implement a queue as a linked list. However, it’s possible to print the current level of the binary tree using a function in C++.
First, use the queue(BFS) for level order traversal of the binary tree by creating an ArrayList of the linked list nodes. Variables can store the queue size and are valuable for retrieving and manipulating all the nodes at each binary tree level.
Now, while the variable that stores the queue size is greater than zero, access the variable and retrieve, print, or manipulate all the nodes by adding their children to the queue.
This recursive solution is fully functional but not as highly effective as a queue or Hashing technique.
#include <iostream>
using namespace std;
class listNode {
public:
int data;
listNode *left, *right;
};
void print_data(listNode* root_node, int level_order);
int lev_height(listNode* node);
listNode* updatedNode(int data);
void printData_LevelOrder(listNode* root_node) {
int heig = lev_height(root_node);
int init;
for (init = 1; init <= heig; init++) print_data(root_node, init);
}
void print_data(listNode* root_node, int level_order) {
// in case of a `null` or empty root
if (root_node == NULL) return;
// in case if root represents `1`
if (level_order == 1) cout << root_node->data << " ";
// in case the root is greater than `1`
else if (level_order > 1) {
print_data(root_node->left, level_order - 1);
print_data(root_node->right, level_order - 1);
}
}
int lev_height(listNode* node_linkedlist) {
// in case of empty or `NULL`
if (node_linkedlist == NULL)
return 0;
else {
int level_leftHeight = lev_height(node_linkedlist->left);
int level_rightHeight = lev_height(node_linkedlist->right);
// in case the left node is greater than the right node
if (level_leftHeight > level_rightHeight) {
return (level_leftHeight + 1);
}
// in case the right node is greater than the left node
else {
return (level_rightHeight + 1);
}
}
}
listNode* updatedNode(int _listdata) {
listNode* list_node = new listNode();
list_node->data = _listdata;
list_node->left = NULL;
list_node->right = NULL;
return (list_node);
}
int main() {
listNode* linkedlistNode = updatedNode(1);
linkedlistNode->left = updatedNode(2);
linkedlistNode->right = updatedNode(3);
linkedlistNode->left->left = updatedNode(4);
linkedlistNode->left->right = updatedNode(5);
cout << "Level by Level Data Insertion to a Binary Tree is Complete! \n";
printData_LevelOrder(linkedlistNode);
return 0;
}
Output:
Level by Level Data Insertion to a Binary Tree is Complete!
1 2 3 4 5
The printLevelOrder and printCurrentLevel are the sub-functions of this approach (using a linked list to print data in the binary tree) which print all the nodes at a given level or print the level order traversal of the binary tree, respectively.
Furthermore, the printLevelOrder sub-function can take advantage of the printCurrentLevel function to print nodes one by one starting from the root at all levels on the binary tree.
The time complexity of the Breath-First Search (BFS) is O(n^2), where the n represents the maximum number of binary tree nodes and O(h) is the auxiliary space required by the C++ program where the h represents the complete height of a binary tree.
Each algorithm you will find in this tutorial can handle every type of binary tree, including; full, perfect, complete, degenerated or pathological, skewed, and balanced binary trees.
Use Hashing Technique to Print Data in Binary Tree Level by Level in C++
As a part of hashing technique, hash tables enable to print data in a binary tree level by level and have proven to be extremely useful data structures that take the O(1) lookup time of a hash table on average.
It can solve several problems related to algorithms and binary data structures extremely efficiently to reduce the time complexity.
The Hashing includes multimap, which allows the mapping of a single key to multiple values and uses it to store binary tree nodes and its level.
The hashing technique uses the binary tree level number (stored in a variable) as a key and prints all the corresponding nodes to each level, starting from the parent node or the first level of the binary tree.
#include <iostream>
// associative container that contains key-value pairs
// search, insert and remove elements in average constant-time complexity
#include <unordered_map>
#include <vector> // initialize the vector contents
using namespace std;
// data structure creation | fulfill the purpose of storing data in a binary
// table
struct _hashnode {
int key;
_hashnode *left, *right;
// `key` -> `_nodekey` will contain all the binary tree info to arrange the
// nodes
_hashnode(int _nodekey) {
this->key = _nodekey;
this->left = this->right = nullptr;
}
};
// enable nodes storage in a map (to traverse the tree in a pre_order fashion)
// corresponding to the node's level
void hash_preorder(_hashnode* hash_root, int level, auto& map) {
// initially: empty binary table
if (hash_root == nullptr) {
return;
}
// current node and its level insertion into the map
map[level].push_back(hash_root->key);
hash_preorder(hash_root->left, level + 1, map);
hash_preorder(hash_root->right, level + 1, map);
}
// recursive function | fulfill the purpose of printing binary tree's level
// order traversal
void traversal_throughHash(_hashnode* hash_root) {
// creation of a `null` or an empty map | to store nodes between the given
// levels of a binary tree
unordered_map<int, vector<int>> map;
/* level-wise insertion of nodes to the map after the tree traversal */
hash_preorder(hash_root, 1, map);
for (int init = 1; map[init].size() > 0; init++) {
cout << "[Binary Tree] Level " << init << ":- ";
for (int juan : map[init]) {
cout << juan << " ";
}
cout << endl;
}
}
int main() {
_hashnode* hash_Root = new _hashnode(15);
hash_Root->left = new _hashnode(10);
hash_Root->right = new _hashnode(20);
hash_Root->left->left = new _hashnode(8);
hash_Root->left->right = new _hashnode(12);
hash_Root->right->left = new _hashnode(16);
hash_Root->right->right = new _hashnode(25);
hash_Root->right->right->right = new _hashnode(30);
traversal_throughHash(hash_Root);
return 0;
}
Output:
[Binary Tree] Level 1:- 15
[Binary Tree] Level 2:- 10 20
[Binary Tree] Level 3:- 8 12 16 25
[Binary Tree] Level 4:- 30
Generally, a binary tree acts as a data structure where the topmost node is the parent or the root node, and each parent node represents a pair of child nodes.
There are four common ways of binary tree traversal, and level-by-level order traversal is one of the most efficient.
It’s a fact that no algorithm that is based on sort by comparison can do better than n log n performance. Each node of the binary tee represents a comparison between its child nodes (ai ≤ aj), and they represent one of the n!.
A binary tree contains n = (2^h) - 1 nodes where h represents the height of the binary tree, and every non-leaf node has both right and left child nodes.
You can determine the height of a binary tree by computing h = [log(n!)] for a tree with n! leaf nodes and h = log(n + 1) height.
Hassan is a Software Engineer with a well-developed set of programming skills. He uses his knowledge and writing capabilities to produce interesting-to-read technical articles.
GitHub