Level Order Traversal Of A Tree In C++
Level Order Traversal Of A Tree
A tree can be traversed using level order and depth first order. In level order traversal, we move level by level that is we visit all the nodes in the same level then move onto the next level. Level order traversal can be achieved using recursion or queue.
Algorithm:
- If the root is NULL, return.
- Otherwise push the root in queue.
- Print the node’s data and add its left and right child.
- Pop the node from the queue.
- Repeat until the queue is empty.
Why Queue is better to traverse than Recursion?
- Queues improves the time complexity because recursion gives the time complexity of O(2^n) in the worst case, whereas queue gives time complexity of O(n).
- Height of the tree is first calculated to print level order but this is not required in queue.
- Implementation is shorter in queues.
Code:
#include<bits/stdc++.h>
using namespace std;
class Tree {
public:
int data;
Tree* left = NULL,*right = NULL;
// Constructor initialised
Tree(int x) {
data = x;
left = NULL;
right = NULL;
}
};
void level_order(Tree *root) {
if (root == NULL) return; // Checking whether NULL
queue<Tree *> q;
q.push(root); // Adding root to queue
while (!q.empty()) {
cout << q.front() -> data << ” “; // Printing Data
// Adding left and right child if not null
if (q.front() -> left != NULL) {
q.push(q.front() -> left);
}
if (q.front() -> right != NULL) {
q.push(q.front() -> right);
}
// Removing the node from queue
q.pop();
}
}
int main() {
Tree *root = new Tree(10);
root -> left = new Tree(20);
root -> right = new Tree(30);
root -> left -> left = new Tree(40);
root -> left -> right = new Tree(50);
level_order(root);
return 0;
}
Output:
10 20 30 40 50
Time Complexity
For Level Order Travesal
Time Complexity
O(n)
Space Complexity
O(n)
