Print Alternate Nodes from all Levels of a Binary Tree

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 level-wise 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);
}

You can also try this code with Online C++ Compiler

Run Code

Output:

8 
3 
1 14 
4 13

Time Complexity 

O(K)

The time complexity for the solution to print alternate nodes level-wise 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 next-level 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 level-wise 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:

• Print Nodes At Distance K From Node
• Kth Ancestor Of A Node In Binary Tree
• Segregate Even And Odd Nodes In A Linked List
   

Recommended Reading:

• Print All Nodes That Are at A Distance of K From the Leaf Node
• Print All Root Leaf Paths With Relative Positions
• Print All Prime Levels of a Binary Tree
• Print Ancestors of A Given Node
• Print Binary Tree Levels in a Sorted Order
• Print All K Sum Levels in a Binary Tree
• Print Cousins of a Given Node in Binary Tree
• Print All Possible N Nodes of a Full Binary Tree
   

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.