Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem statement
3.
Approach
3.1.
Algorithm
3.2.
Code
4.
Frequently Asked Questions
4.1.
What is a Binary tree?
4.2.
What is a queue?
4.3.
Is there any other way also to solve this problem?
5.
Conclusion
Last Updated: Mar 27, 2024

Print Alternate Nodes from all Levels of a Binary Tree

Author Apoorv
1 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

Binary Trees are popular Data Structures and have a wide range of applications throughout various fields. Binary Trees are also important when it comes to interviews with top tech companies. A mastery of Binary Trees could help us solve a lot of problems. In this article, we are going to take a look at one such problem.

Problem statement

In this question, we are given a binary tree and we have to print all the nodes level-wise from left to right but in every level, we have to print only the alternate nodes.

 

Example

Input

Binary Tree

 

Output:

8

3

1 14

4 13

Like here in level 1 we can print 8 than in level 2 we will print 3 then we will not print next node that is 10 similarly in the third level we will print 1 then 14 leaving 6 and in the final level, we will print 4 and 13 leaving 7 because we have to print alternate nodes in every level

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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

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:

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.

Previous article
Difference between Sums of Odd Level and Even Level Nodes of a Binary Tree
Next article
Print all possible N-nodes Full Binary Trees
Live masterclass