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
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
46+ registered 