Level Order Traversal without a Queue: Recursive Approach
In this approach, you essentially use a recursive function to visit nodes level by level and store the node values in the 2D vector where the row corresponds to the level and the columns are the nodes in the level.
Algorithm
This methods requires two functions, one is the recursive function that takes the reference to the tree and the 2D vector and insert the nodes in the array at corresponding rows and the other is the one which calls this recursive function and then prints the level order.
Recursive Function
- This function takes the pointer to the node, current level and the reference to the 2D vector.
- First, we check if the current node is NULL. If it is NULL, we return to the caller. Otherwise.
- Push the current node value to that row of 2D vector which is equal to the current level.
- Then, call this function for node->left with level = level + 1.
- Again call this function for node->right with level = level + 1.
Calling Function
- First check if the tree is empty or not. If not then
- Create a 2D vector for storing the level order values.
- Call the recursive function and pass the reference to this vector.
- Print the vector.
C++ Program to Implement the Level Order Binary Tree Traversal without Queue
// C++ program to demonstrate how to implement the level
// order traversal without using queue
#include <iostream>
#include <vector>
using namespace std;
// tree noode
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x): val(x), left(NULL), right(NULL){}
};
// recursive function as level order traversal helper
// function
void levelOrderHelper(TreeNode* node, int level,
vector<vector<int> >& results)
{
if (!node)
return;
// Ensure the vector is large enough to include this
// level
if (level == results.size())
// Add a new level
results.push_back(vector<int>());
// pushing current node value
results[level].push_back(node->val);
// Recurse to the left and right, increasing the level
levelOrderHelper(node->left, level + 1, results);
levelOrderHelper(node->right, level + 1, results);
}
// parent level order traversal function
void levelOrderTraversal(TreeNode* root)
{
// creating vctor to store result
vector<vector<int> > results;
// calling helper function
levelOrderHelper(root, 0, results);
// printing level order
for (const auto& level : results) {
for (int val : level) {
cout << val << " ";
}
}
}
int main()
{
// Create nodes
TreeNode* root = new TreeNode(8);
root->left = new TreeNode(3);
root->right = new TreeNode(10);
root->left->left = new TreeNode(1);
root->left->right = new TreeNode(6);
root->right->right = new TreeNode(14);
root->left->right->left = new TreeNode(4);
root->left->right->right = new TreeNode(7);
root->right->right->left = new TreeNode(13);
// Perform level order traversal without a queue
cout << "Level order traversal output:\n";
levelOrderTraversal(root);
return 0;
}
Output
Level order traversal output: 8 3 10 1 6 14 4 7 13
Binary Tree Level Order Traversal in C++
Trees are the type of data structure that stores the data in the form of nodes having a parent or children or both connected through edges. It leads to a hierarchical tree-like structure that can be traversed in multiple ways such as —preorder, inorder, postorder, and level order. A binary tree is a tree data structure a node can only have 2 children at max.
In this article, we will learn about level order binary tree traversal in C++, how to implement it using a C++ program and analyze its time and space complexity.