Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Approach
2.1.
Algorithm
2.2.
Code
2.3.
Complexity Analysis
3.
Frequently Asked Questions
3.1.
What is a Binary tree?
3.2.
What is a queue?
3.3.
Is there any other way to print a tree in a specific level order traversal?
4.
Conclusion
Last Updated: Mar 27, 2024

Specific Level Order Traversal of Binary Tree

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

Introduction

Given a binary tree, you have to do a level order traversal for the binary tree in a specific order that is in every level print elements in the given order mentioned:

The first element of the level,

Last element of the level,

The second element of the level,

Second last element in the level,

The third element in the level,

Third last element in the level,

(n/2)th element of the level,

(n/2)th+1 element of the level.

Also see, Perfect Binary Tree Specific Level Order Traversal

Let's understand the same with an example.

 

Example 1

Input

binary tree

Source: Wikipedia

Output

1 2 3 17 7 19 36 25 100

Explanation:

First level 1

Second level 2(left) , 3(right)

Third level 17(left) , 7(right) , 19(left) , 36(right)

Fourth level 25(left), 100(right) 

Must Recommended Topic, Binary Tree Postorder Traversal.

Approach

The approach here is to make the binary tree into a complete binary tree by pushing null pointers at nodes with no children and then perform the level order traversal by making two queues such that one queue stores elements from the left side and the other queue stores element from the right side. While doing level Order traversal, just print the values alternately from both queues.

 

Algorithm

  • Perform the level order traversal on the tree and make sure while doing traversal if you encounter a tree node with no child tree node push null node as a child tree node in the queue
  • For doing traversals, maintain two queues, one for the left half of the level and the other for the right half of the level.
  • Calculate the height of the binary tree using recursion
  • Run a while loop till the height becomes 0 for every level
  • In every iteration, pop out the first node from both queues.
  • Check if the popped tree node is not null, then print their values and push their child nodes in the queue; otherwise, if a popped node is null, then simply push two times null tree node in their respective queue form which it was popped

 

Code

import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.*;
 
class Main{
     
// Structure of treenode
static class treenode
{
    int data;
    treenode left = null;
    treenode right = null;
}
  
// Creating a new node 
static treenode newNode(int value)
{
     
    // Allocating memory to a new node
    treenode node = new treenode();
    node.data = value;
    node.left = null;
    node.right = null;
    return node;
}
 
// This function returns height of a complete binary tree
static int hei(treenode root)
{
    if (root == null)
        return 0;
         
    return 1 + Math.max(hei(root.left),
                        hei(root.right));
}
  
// Printing the nodes in a specific level Order Traversal for a given tree
static void SpecificLevelOrderTraversal(Queue<treenode> first,
                                    Queue<treenode> second,
                                    int height)
{
    while (height != 0)
    {
         
        // Take out the front element from both the queue
        treenode a = first.poll();
        treenode b = second.poll();
         
        // Check if a exist or not 
        if (a == null)
        {
             
            // Here a is null so put both the child as null pointer 
            first.add(null);
            first.add(null);
        }
        else
        {
             
            // Print the value of the node and then push their children both left and right
            System.out.print(a.data + " ");
            first.add(a.left);
            first.add(a.right);
        }
         
        // Check b exist or not   
        if (b == null)
        {   
             
            // Here a is null so put both the child as null pointer 
            second.add(null);
            second.add(null);
        }
        else
        {
             
            // Print the value of the node and then push their children both left and right
            System.out.print(b.data + " ");
            second.add(b.right);
            second.add(b.left);
        }

        // Decrease by 1 unit   
        height -= 1;     
    }
}
 
// Main Code    
public static void main (String[] args)
{
     
    // Formation of a tree
    //First level
    treenode root = newNode(1);

    // Second level
    root.left = newNode(2);
    root.right = newNode(3);

    // Third level 
    root.left.left = newNode(17);
    root.left.right = newNode(19);
    root.right.left = newNode(36);
    root.right.right = newNode(7);
     
    // Fourth level
    root.left.left.left = newNode(25);
    root.left.left.right = newNode(100);

    // Tree
    //      1
    //    /   \
    //   2    3
    //  / \   / \
    //  17 19 36 7
    //  /\
    // 25  100 

    // Queue initialization
    Queue<treenode> first = new LinkedList<>();
    Queue<treenode> second = new LinkedList<>();
     
    int height = 0;
     
    // Check top root manually
    if (root != null)
    {
        System.out.print(root.data + " ");
         
        first.add(root.left);
        second.add(root.right);
          
        // Calculating the height  
        height = hei(root);
        height = (int)Math.pow(2, (height - 1)) - 1;
    }
     
    // Function Call to print specific level order traversal
    SpecificLevelOrderTraversal(first, second, height);
}
}

Output:

1 2 3 17 7 19 36 25 100

 

Complexity Analysis

Time Complexity 

O(N)

The time complexity for printing a tree in a specific Level Order Traversal is O(N), where ‘N’ is the number of nodes lets understand this bit more first, we are calculating the height of a tree, which will cost O(N) time complexity, then in Specific Level Order Traversal, this function we are iterating on every level to print the elements of that level in a specific order which will again cost O(N) time complexity.

So the total time complexity will be O(N) + O(N) = 2 * O(N) or ~ O(N) 

 

Space Complexity 

O(N)

The space complexity for the above solution of printing a tree in a specific Level Order Traversal is O(N), where ‘N’ is the number of nodes since we are using extra space, that is, two queues for storing the nodes of a binary tree if we consider the tree has a complete binary tree than half of the nodes are stored in each queue so the total cost to store the tree will be number of nodes present in the tree that is O(N)

Check out this problem - Mirror A Binary Tree

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

Frequently Asked Questions

What is a Binary tree?

A generic tree with at most two 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 to print a tree in a specific level order traversal?

Yes, we can store every level element in a linear array, and then while printing we can use the concept of two-pointer to iterate alternately from the left side and right side 

 

Conclusion

In this blog, we solved the problem of printing the nodes of a binary tree level-wise in a specific order

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.To be more confident in data structures and algorithms, try out our DS and Algo Courses

Recommended Reading:

Recommended problems -

 

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, 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.

Cheers!

Live masterclass