Print Alternate Levels of a Binary Tree

by · January 21, 2021

“Print Alternate Levels of a Binary Tree” is a simple modification of level order tree traversal algorithm. Here, we are given a Binary Tree and our task is to write a program to print alternate levels of a Binary Tree.

Print Alternate Levels of a Binary Tree
Alternate Level of Binary Tree

Again, we can solve this problem using previous discussed two methods.

Method 1: Brute-Force Approach

The simplest solution to print alternate level order tree traversal is to traverse and print the nodes at level 1, then traverse and print the nodes at level 3 and so on; till all the alternate level nodes are not traversed and printed.

C++ Program to Print Alternate Levels of a Binary Tree is as follows:

/* C++ Program to Print Alternate Level of a Binary Tree*/
#include<bits/stdc++.h>
using namespace std;

typedef struct Node
{
    int data;
    struct Node *left;
    struct Node *right;
    Node(int ele)
    {
        data = ele;
        left = NULL;
        right = NULL;
    }
} Node;


/* Function to Compute height of a Binary Tree */
int height(Node *root)
{
    /* If tree is empty, height will be 0 */
    if(root == NULL)
    {
        return 0;
    }
    else
    {
        /* Compute Height of Left Subtree */
        int leftHeight = height(root -> left);
        
        /* Compute Height of Right Subtree */
        int rightHeight = height(root -> right);
        
        /* Return max of height of subtree and right subtree + 1 */
        return max(leftHeight,rightHeight) + 1;
    }
}

/* Function to Print Nodes of a Particular Level */
void printLevel(Node *root, int level)
{
    if(root == NULL)
    return;
    
    if(level == 1)
    cout<<root -> data<< " ";
    else if(level > 1)
    {
        printLevel(root -> left,level-1);
        printLevel(root -> right, level-1);
    }
}

/* Function to Print Alternate Level of a Binary Tree */
void printAlternate(Node *root)
{
    /* Basic Test Case Scenerio */
    if(root == NULL)
    return;
    
    /* Compute Height and print Level by Level */
    int h = height(root);
    for(int i = 1; i <= h; i=i+2)
    printLevel(root,i);
}

int main()
{
    /* Creating a Binary tree and inserting some nodes in it */
    Node *root = NULL;
    
    root = new Node(1);
    root -> left = new Node(2);
    root -> right = new Node(3);
    root -> left -> left = new Node(4);
    root -> left -> right = new Node(5);
    root -> right -> left = new Node(6);
    root -> right -> right = new Node (7);
    root -> left -> right -> left = new Node(8);
    root -> right -> left -> right = new Node(9);
    
    /* Calling function to Print Alternate Level of a Binary Tree */
    cout<<"The Nodes at Alternate Levels of the Given Binary Tree :\n";
    printAlternate(root);
}

OUTPUT:

The Nodes at Alternate Levels of the Given Binary Tree :
1 4 5 6 7

Method 2: Using Queue

The steps required to print alternate levels of Binary Tree are as follows:

  • Create two queues: que1 and que2.
  •  Push root node into que1.
  • Until both queues are not empty, perform following steps:
    • Until que1 is not empty, perform following steps:
      • Print Front node of que1.
      • If left child of front node exists, then, push left child into que2.
      • If right child of front node exists, then, push right child into que2.
      • Pop out front node.
    • Until que2 is not empty, perform following steps:
      • If left child of front node exists, then, push left child into que1.
      • If right child of front node exists, then, push right child into que1.
      • Pop out front node.

C++ Program to print alternate levels of Binary Tree is as follows:

/* C++ Program to Print Alternate Level of Binary Tree */
#include<bits/stdc++.h>
using namespace std;

typedef struct Node
{
    int data;
    struct Node *left;
    struct Node *right;
    Node(int ele)
    {
        data = ele;
        left = NULL;
        right = NULL;
    }
} Node;

/* Function to Print Alternate Level of Binary Tree*/
void printAlternate(Node *root)
{
    /* Basic Test Case Scenerio */
    if(root == NULL)
    return;
    
    queue <Node*> que1;
    queue <Node*> que2;
    
    que1.push(root);
    
    while(!que1.empty() || !que2.empty())
    {
        while(!que1.empty())
        {
            Node *temp = que1.front();
            cout<<temp->data<<" ";
            if(temp -> left)
            que2.push(temp -> left);
            if(temp -> right)
            que2.push(temp -> right);
            que1.pop();
        }
        while(!que2.empty())
        {
            Node *temp = que2.front();
            if(temp -> left)
            que1.push(temp -> left);
            if(temp -> right)
            que1.push(temp -> right);
            que2.pop();
        }
    }
}

int main()
{
    /* Creating a Binary tree and inserting some nodes in it */
    Node *root = NULL;
    
    root = new Node(1);
    root -> left = new Node(2);
    root -> right = new Node(3);
    root -> left -> left = new Node(4);
    root -> left -> right = new Node(5);
    root -> right -> left = new Node(6);
    root -> right -> right = new Node (7);
    root -> left -> right -> left = new Node(8);
    root -> right -> left -> right = new Node(9);
    
    /* Calling function for Level Order Traversal */
    cout<<"The Alternate Levels of Given Binary Tree are:\n";
    printAlternate(root);
}

OUTPUT:

The Alternate Levels of Given Binary Tree are:
1 4 5 6 7

Related Posts:

  1. Introduction to Tree Data Structure
  2. Binary Tree Traversals
  3. Print All Leaf Nodes of a Binary Tree
  4. Count Number of Nodes in a Binary Tree
  5. Maximum Width of Binary Tree
  6. Level Order Tree Traversal
  7. Left View of Binary Tree
  8. Right View of Binary Tree
  9. Compute Height of Binary Tree
  10. Inorder Tree Traversal Using Stack
  11. Preorder Tree Trasversal Using Stack
  12. Postorder Tree Traversal Using Stack
  13. Vertical Order Tree Traversal
  14. Top View of Binary Tree
  15. Bottom View of Binary Tree
  16. Delete Complete Binary Tree
  17. Check if two trees are mirror Trees of Each Other
  18. Convert Binary Tree to its Mirror Tree
  19. Check if Binary Tree is Symmetric or Not
  20. Print All Root to Leaf Paths in a Binary Tree

You may also like...