Approach
This problem can be solved using basic level order traversal. While doing level order traversal, print the alternate nodes in every level. For level order traversal we can use queue data structure. In order to print alternate nodes stored in the queue we can use the concept of flag variable when the flag is set we will print the element and make the flag off in the next iteration and in a similar fashion every alternate time when the flag will be in set position then it will simply print the node value. There is one more technique to print the alternate nodes in a level that is by checking that whether the node in the current level appeared even number of times or an odd number of times, then for every alternate time we will print the value in alternate nodes as implemented in code given below.
Algorithm

Make a queue for doing level order traversal
 Push the root node at the beginning of the queue
 Now use the while loop until the size of the queue becomes 0
 Find the size of the queue this will tell the total number of elements present in that particular level of the tree
 Run a for loop in the complete level and pop out the element and save the value in the current variable
 While this iteration print element alternately that is when i is even in the loop print the value of current
 After printing simultaneously push the child nodes that are the left child and right child from the back of the queue before pushing check whether that node exit or not if the node exits then only perform the push operation
 Ultimately this will print alternate nodes levelwise for a binary tree
Code
#include <bits/stdc++.h>
using namespace std;
// Structure of a Node in a binary tree
struct ListNode {
int data;
ListNode* left;
ListNode* right;
ListNode(int value)
{
data = value;
left = right = NULL;
}
};
// Printing of a alternate nodes of a binary tree
void PrintAlternateNodes(ListNode* root)
{
// Store nodes of each level
queue<ListNode*> que;
que.push(root);
while (!que.empty()) {
// Store count of nodes of current level
int n = que.size();
// Print alternate nodes of the current level
for (int i = 0; i < n; i++) {
ListNode* current = que.front();
que.pop();
/*
Here for every even value of i print the node
and for odd dont print which will ultimately lead
to print alternate nodes
*/
if (i % 2 == 0) {
cout << current>data << " ";
}
// Pushing the child nodes of the current node
if (current>left) que.push(current>left);
if (current>right) que.push(current>right);
}
cout << endl;
}
}
int main()
{
ListNode* root;
// Formation of a tree
root = new ListNode(8);
root>left = new ListNode(3);
root>right = new ListNode(10);
root>left>left = new ListNode(1);
root>left>right = new ListNode(6);
root>right>right = new ListNode(14);
root>left>right>left = new ListNode(4);
root>left>right>right = new ListNode(7);
root>right>right>left = new ListNode(13);
// Print alternate nodes
PrintAlternateNodes(root);
}
Output:
8
3
1 14
4 13
Time Complexity
O(K)
The time complexity for the solution to print alternate nodes levelwise in a binary tree will be O(K), where ‘K’ is the number of nodes at each level as queue can store a maximum of two levels node at a time (the level which is under processing state and their child or nextlevel nodes). Since we are iterating on the size of the queue in a for loop so it will cost the O(K) time complexity in the worst case where k is the size of the queue or the element present at that particular level.
Space Complexity
O(K)
The space complexity to print alternate nodes in a binary tree levelwise is O(K) where ‘K’ is the number of nodes at each level since we are using a queue to store the nodes.
Frequently Asked Questions
What is a Binary tree?
A generic tree with at most 2 child nodes.
What is a queue?
A data structure that stores elements in a linear fashion and elements can be inserted from the backside and deleted from the front side.
Is there any other way also to solve this problem?
We can use recursion to do level order traversal but that will again cost quadratic time complexity that is O(N ^ 2).
Conclusion
In this blog, we solved the problem of printing alternate nodes in all the levels of a binary tree.
If you want to learn more about Binary trees and want to practice some questions which require you to take your basic knowledge of Binary trees a notch higher, then you can visit our Guided Path for Binary Trees on Coding Ninjas Studio
Recommended Problems:
Recommended Reading:
Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.