Posted on by Kalkicode
Code Queue

# Print binary tree level in sorted order

The problem at hand is to print the nodes of a binary tree in sorted order at each level. We are given a binary tree, and for each level of the tree, we need to print the nodes in ascending order.

## Problem Statement

Given a binary tree, we need to print the nodes at each level in sorted order. For example, consider the following binary tree:

``````
1
/ \
3   2
/   / \
4   9   6
/ \ / \   \
7   8 2   4  10
``````

The output for this tree would be:

``````Sorted Level
[ 1 ]
[ 2 3 ]
[ 4 6 9 ]
[ 2 4 7 8 10 ]
``````

## Idea to Solve

To solve this problem, we can use a breadth-first search (BFS) approach. We will traverse the binary tree level by level using a queue. However, instead of just a normal queue, we will use a custom queue implementation called `MyQueue`, which can add elements in a sorted order. This custom queue will be used to store nodes in ascending order at each level.

## Pseudocode

1. Create a custom queue `MyQueue` with methods `enqueue`, `dequeue`, `sort_enqueue`, and `is_empty`.
2. Create a method `sorted_level()` in the `BinaryTree` class to perform the BFS and print the nodes in sorted order at each level.
3. Initialize a counter variable `level_counter` to 1.
4. Enqueue the root node of the binary tree with its level into the custom queue.
5. While the custom queue is not empty:
• Dequeue a node from the front of the custom queue.
• If the dequeued node's level is different from `level_counter`, it means we have traversed all nodes at the current level. Print the nodes stored in the `priority` queue and update `level_counter` to the dequeued node's level.
• Enqueue the left child and right child (if they exist) of the dequeued node into the custom queue with their corresponding levels.
• Enqueue the dequeued node into the `priority` queue using `sort_enqueue`.
6. After the loop, print the remaining nodes in the `priority` queue.

## Algorithm Explanation

The provided code already implements the above pseudocode using the `MyQueue` class and the `sorted_level()` method. The custom queue `MyQueue` is implemented in such a way that it can add elements in sorted order based on the node data.

## Code Solution

``````// C program
// Print binary tree level in sorted order

#include <stdio.h>

#include <stdlib.h>

//Node of binary tree
struct Node
{
int data;
struct Node *left, *right;
};

struct MyQueue
{
int level;
struct Node *element;
struct MyQueue *next;
};

//Create a binary tree nodes and node fields (data,pointer)
//And returning the reference of newly nodes
struct Node * insert(int data)
{
//create dynamic memory to new binary tree node
struct Node * new_node = (struct Node * ) malloc(sizeof(struct Node));
if (new_node != NULL)
{
//Set node value
new_node->data = data;
new_node->left = NULL;
new_node->right = NULL;
}
else
{
printf("Memory Overflow\n");
}
//return reference
return new_node;
}

//Create a queue node and returns this node
struct MyQueue *enqueue(struct Node *tree_node)
{
//Make a new Queue node
struct MyQueue *new_node = (struct MyQueue * ) malloc(sizeof(struct MyQueue));

if (new_node != NULL)
{
//Set node values
new_node->element = tree_node;
new_node->next = NULL;
}
else
{
printf("Memory Overflow\n");

}
return new_node;
}
//Remove a queue elements
void dequeue(struct MyQueue ** front)
{
if ( * front != NULL)
{
struct MyQueue *remove = *front;
//Visit to next node
*front = remove->next;
remove->element = NULL;
remove->next = NULL;
//free node
free(remove);
remove = NULL;
}
}

void priority_queue(struct MyQueue **result,struct Node *tree_node)
{
//Make a new Queue node
struct MyQueue *new_node = (struct MyQueue * ) malloc(sizeof(struct MyQueue));

if (new_node != NULL)
{
new_node->element = tree_node;
new_node->next = NULL;

if(*result==NULL)
{
//When first node of queue
*result = new_node;
}
else if((*result)->element->data >= tree_node->data)
{
new_node->next = *result;

*result = new_node;
}
else
{
struct MyQueue*temp = *result;

//Find insert node location
while(temp->next!=NULL && temp->next->element->data < tree_node->data)
{
temp = temp->next;
}

new_node->next = temp->next;

temp->next = new_node;
}
}
else
{
printf("Memory Overflow\n");

}

}
//Print sorted level of binary tree
void show_level(struct MyQueue**result)
{
if(*result==NULL)
{
return;
}
struct MyQueue*temp=*result;
printf("\n[");
while(*result!=NULL)
{
temp = *result;

*result = temp->next;

printf(" %d",temp->element->data);
temp->element = NULL;
free(temp);
temp = NULL;
}
printf(" ]");
}

//Get sorted level in binary tree
void sorted_level(struct Node *root)
{
if (root != NULL)
{
//create queue variables
struct MyQueue *front = NULL, *tail = NULL;

//This are used to store sorted level of tree element
//like priority queue
struct MyQueue *result = NULL;

//Get first node of tree
front = enqueue(root);
//Start level of first node is one
front->level = 1;

tail = front;

int level_counter = 1;

struct Node *node = root;

printf("\nSorted Level ");

//Execute loop until the queue is not empty
while (front != NULL)
{

node = front->element;

if (node->left != NULL)
{
tail->next = enqueue(node->left);

tail->next->level = front->level + 1;

tail = tail->next;
}
if (node->right != NULL)
{
tail->next = enqueue(node->right);

tail->next->level = front->level + 1;
tail = tail->next;
}
if (front->level != level_counter)
{

//When level change
level_counter = front->level;

//Display sorted elemet
show_level(&result);
}

//Add current node into priority queue
priority_queue(&result,node);
//remove element of queue
dequeue( &front);
}

tail = NULL;

//Display sorted elemet in last level
show_level(&result);
}
else
{
}
}
int main()
{
struct Node *root = NULL;
/*
Construct Binary Tree
-----------------------
1
/    \
3       2
/       / \
4       9   6
/  \    / \    \
7    8  2   4    10
*/
root = insert(1);
root->left = insert(3);
root->right = insert(2);
root->right->right = insert(6);
root->right->left = insert(9);
root->right->left->left = insert(2);
root->left->left = insert(4);
root->left->left->left = insert(7);
root->left->left->right = insert(8);
root->right->left->right = insert(4);
root->right->right->right = insert(10);

//level element in sorted order
sorted_level(root);

return 0;
}``````

#### Output

``````Sorted Level
[ 1 ]
[ 2 3 ]
[ 4 6 9 ]
[ 2 4 7 8 10 ]``````
``````/*
Java program
Print binary tree level in sorted order
*/
//Binary Tree node
class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
//set node value
this.data = data;
this.left = null;
this.right = null;
}
}
// Queue Node
class QueueNode
{
public TreeNode element;
public QueueNode next;
public int level;
public QueueNode(TreeNode element, int level)
{
this.element = element;
this.next = null;
this.level = level;
}
}
//Define custom queue class
class MyQueue
{
public QueueNode front;
public QueueNode tail;
public MyQueue()
{
this.front = null;
this.tail = null;
}
//Add a new node at last of queue
public void enqueue(TreeNode element, int level)
{
QueueNode new_node = new QueueNode(element, level);
if (this.front == null)
{
//When first node of queue
this.front = new_node;
}
else
{
this.tail.next = new_node;
}
this.tail = new_node;
}
//Delete first node of queue
public void dequeue()
{
if (this.front != null)
{
if (this.tail == this.front)
{
this.tail = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
}
}
//Add a new node in sorted order
public void sort_enqueue(TreeNode element)
{
QueueNode new_node = new QueueNode(element, 0);
if (this.front == null)
{
//When first node of queue
this.front = new_node;
this.tail = new_node;
}
else if (this.front.element.data >= element.data)
{
new_node.next = this.front;
this.front = new_node;
}
else if (this.tail.element.data <= element.data)
{
this.tail.next = new_node;
this.tail = new_node;
}
else
{
//When need to add node at intermediate position
QueueNode temp = this.front;
//Find location to add new node
while (temp.next != null && temp.next.element.data < element.data)
{
temp = temp.next;
}
new_node.next = temp.next;
temp.next = new_node;
}
}
public boolean is_empty()
{
if (this.front == null)
{
return true;
}
else
{
return false;
}
}
public void show_level()
{
if (this.front == null)
{
return;
}
QueueNode temp = null;
System.out.print("\n[");
while (this.is_empty() == false)
{
temp = this.front;
System.out.print(" " + temp.element.data);
temp.element = null;
this.dequeue();
}
System.out.print(" ]");
}
}
class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
//set initial tree root to null
this.root = null;
}
//Display Inorder view of binary tree
public void inorder(TreeNode node)
{
if (node != null)
{
// Executing left subtree
this.inorder(node.left);
//Print node value
System.out.print("  " + node.data);
// Executing right subtree
this.inorder(node.right);
}
}
public void sorted_level()
{
if (this.root == null)
{
System.out.print("\n Empty Binary Tree \n");
}
else
{
//Get top node in tree
TreeNode node = this.root;
//Define some useful counter variables
int level_counter = 1;
int node_level = 0;
//Create a normal Queue
MyQueue queue = new MyQueue();
//Create a sorted priority Queue
MyQueue priority = new MyQueue();
//Add first node at the level of one
queue.enqueue(node, level_counter);
System.out.print("\nSorted Level  ");
//Execute loop until the queue is not empty
while (queue.is_empty() == false)
{
node = queue.front.element;
node_level = queue.front.level;
if (node.left != null)
{
queue.enqueue(node.left, node_level + 1);
}
if (node.right != null)
{
queue.enqueue(node.right, node_level + 1);
}
if (node_level != level_counter)
{
level_counter = queue.front.level;
priority.show_level();
}
priority.sort_enqueue(node);
//remove element into queue
queue.dequeue();
}
priority.show_level();
}
}
public static void main(String[] args)
{
//Make object of Binary Tree
BinaryTree tree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
1
/    \
3       2
/       / \
4       9   6
/  \    / \    \
7    8  2   4    10
*/
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(3);
tree.root.right = new TreeNode(2);
tree.root.right.right = new TreeNode(6);
tree.root.right.left = new TreeNode(9);
tree.root.right.left.left = new TreeNode(2);
tree.root.left.left = new TreeNode(4);
tree.root.left.left.left = new TreeNode(7);
tree.root.left.left.right = new TreeNode(8);
tree.root.right.left.right = new TreeNode(4);
tree.root.right.right.right = new TreeNode(10);
//level element in sorted order
tree.sorted_level();
}
}``````

#### Output

``````Sorted Level
[ 1 ]
[ 2 3 ]
[ 4 6 9 ]
[ 2 4 7 8 10 ]``````
``````//Include header file
#include <iostream>

using namespace std;
/*
C++ program
Print binary tree level in sorted order
*/
//Binary Tree node
class TreeNode
{
public: int data;
TreeNode *left;
TreeNode *right;
TreeNode(int data)
{
//set node value
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
// Queue Node
class QueueNode
{
public: TreeNode *element;
QueueNode *next;
int level;
QueueNode(TreeNode *element, int level)
{
this->element = element;
this->next = NULL;
this->level = level;
}
};
//Define custom queue class
class MyQueue
{
public: QueueNode *front;
QueueNode *tail;
MyQueue()
{
this->front = NULL;
this->tail = NULL;
}
//Add a new node at last of queue
void enqueue(TreeNode *element, int level)
{
QueueNode *new_node = new QueueNode(element, level);
if (this->front == NULL)
{
//When first node of queue
this->front = new_node;
}
else
{
this->tail->next = new_node;
}
this->tail = new_node;
}
//Delete first node of queue
void dequeue()
{
if (this->front != NULL)
{
QueueNode *temp = this->front;
if (this->tail == this->front)
{
this->tail = NULL;
this->front = NULL;
}
else
{
this->front = this->front->next;
}
free(temp);
temp = NULL;
}
}
//Add a new node in sorted order
void sort_enqueue(TreeNode *element)
{
QueueNode *new_node = new QueueNode(element, 0);
if (this->front == NULL)
{
//When first node of queue
this->front = new_node;
this->tail = new_node;
}
else if (this->front->element->data >= element->data)
{
new_node->next = this->front;
this->front = new_node;
}
else if (this->tail->element->data <= element->data)
{
this->tail->next = new_node;
this->tail = new_node;
}
else
{
//When need to add node at intermediate position
QueueNode *temp = this->front;
//Find location to add new node
while (temp->next != NULL && temp->next->element->data < element->data)
{
temp = temp->next;
}
new_node->next = temp->next;
temp->next = new_node;
}
}
bool is_empty()
{
if (this->front == NULL)
{
return true;
}
else
{
return false;
}
}
void show_level()
{
if (this->front == NULL)
{
return;
}
QueueNode *temp = NULL;
cout << "\n[";
while (this->is_empty() == false)
{
temp = this->front;
cout << " " << temp->element->data;
temp->element = NULL;
this->dequeue();
}
cout << " ]";
}
};
class BinaryTree
{
public: TreeNode *root;
BinaryTree()
{
//set initial tree root to null
this->root = NULL;
}
//Display Inorder view of binary tree
void inorder(TreeNode *node)
{
if (node != NULL)
{
// Executing left subtree
this->inorder(node->left);
//Print node value
cout << "  " << node->data;
// Executing right subtree
this->inorder(node->right);
}
}
void sorted_level()
{
if (this->root == NULL)
{
cout << "\n Empty Binary Tree \n";
}
else
{
//Get top node in tree
TreeNode *node = this->root;
//Define some useful counter variables
int level_counter = 1;
int node_level = 0;
//Create a normal Queue
MyQueue *queue = new MyQueue();
//Create a sorted priority Queue
MyQueue *priority = new MyQueue();
//Add first node at the level of one
queue->enqueue(node, level_counter);
cout << "\nSorted Level  ";
//Execute loop until the queue is not empty
while (queue->is_empty() == false)
{
node = queue->front->element;
node_level = queue->front->level;
if (node->left != NULL)
{
queue->enqueue(node->left, node_level + 1);
}
if (node->right != NULL)
{
queue->enqueue(node->right, node_level + 1);
}
if (node_level != level_counter)
{
level_counter = queue->front->level;
priority->show_level();
}
priority->sort_enqueue(node);
//remove element into queue
queue->dequeue();
}
priority->show_level();
}
}
};
int main()
{
//Make object of Binary Tree
BinaryTree *tree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
1
/    \
3       2
/       / \
4       9   6
/  \    / \    \
7    8  2   4    10
*/
tree->root = new TreeNode(1);
tree->root->left = new TreeNode(3);
tree->root->right = new TreeNode(2);
tree->root->right->right = new TreeNode(6);
tree->root->right->left = new TreeNode(9);
tree->root->right->left->left = new TreeNode(2);
tree->root->left->left = new TreeNode(4);
tree->root->left->left->left = new TreeNode(7);
tree->root->left->left->right = new TreeNode(8);
tree->root->right->left->right = new TreeNode(4);
tree->root->right->right->right = new TreeNode(10);
//level element in sorted order
tree->sorted_level();
return 0;
}``````

#### Output

``````Sorted Level
[ 1 ]
[ 2 3 ]
[ 4 6 9 ]
[ 2 4 7 8 10 ]``````
``````//Include namespace system
using System;

/*
C# program
Print binary tree level in sorted order
*/

//Binary Tree node
class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
//set node value
this.data = data;
this.left = null;
this.right = null;
}
}
// Queue Node
class QueueNode
{
public TreeNode element;
public QueueNode next;
public int level;
public QueueNode(TreeNode element, int level)
{
this.element = element;
this.next = null;
this.level = level;
}
}
//Define custom queue class
class MyQueue
{
public QueueNode front;
public QueueNode tail;
public MyQueue()
{
this.front = null;
this.tail = null;
}
//Add a new node at last of queue
public void enqueue(TreeNode element, int level)
{
QueueNode new_node = new QueueNode(element, level);
if (this.front == null)
{
//When first node of queue
this.front = new_node;
}
else
{
this.tail.next = new_node;
}
this.tail = new_node;
}
//Delete first node of queue
public void dequeue()
{
if (this.front != null)
{
if (this.tail == this.front)
{
this.tail = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
}
}
//Add a new node in sorted order
public void sort_enqueue(TreeNode element)
{
QueueNode new_node = new QueueNode(element, 0);
if (this.front == null)
{
//When first node of queue
this.front = new_node;
this.tail = new_node;
}
else if (this.front.element.data >= element.data)
{
new_node.next = this.front;
this.front = new_node;
}
else if (this.tail.element.data <= element.data)
{
this.tail.next = new_node;
this.tail = new_node;
}
else
{
//When need to add node at intermediate position
QueueNode temp = this.front;
//Find location to add new node
while (temp.next != null && temp.next.element.data < element.data)
{
temp = temp.next;
}
new_node.next = temp.next;
temp.next = new_node;
}
}
public Boolean is_empty()
{
if (this.front == null)
{
return true;
}
else
{
return false;
}
}
public void show_level()
{
if (this.front == null)
{
return;
}
QueueNode temp = null;
Console.Write("\n[");
while (this.is_empty() == false)
{
temp = this.front;
Console.Write(" " + temp.element.data);
temp.element = null;
this.dequeue();
}
Console.Write(" ]");
}
}
class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
//set initial tree root to null
this.root = null;
}
//Display Inorder view of binary tree
public void inorder(TreeNode node)
{
if (node != null)
{
// Executing left subtree
this.inorder(node.left);
//Print node value
Console.Write("  " + node.data);
// Executing right subtree
this.inorder(node.right);
}
}
public void sorted_level()
{
if (this.root == null)
{
Console.Write("\n Empty Binary Tree \n");
}
else
{
//Get top node in tree
TreeNode node = this.root;
//Define some useful counter variables
int level_counter = 1;
int node_level = 0;
//Create a normal Queue
MyQueue queue = new MyQueue();
//Create a sorted priority Queue
MyQueue priority = new MyQueue();
//Add first node at the level of one
queue.enqueue(node, level_counter);
Console.Write("\nSorted Level  ");
//Execute loop until the queue is not empty
while (queue.is_empty() == false)
{
node = queue.front.element;
node_level = queue.front.level;
if (node.left != null)
{
queue.enqueue(node.left, node_level + 1);
}
if (node.right != null)
{
queue.enqueue(node.right, node_level + 1);
}
if (node_level != level_counter)
{
level_counter = queue.front.level;
priority.show_level();
}
priority.sort_enqueue(node);
//remove element into queue
queue.dequeue();
}
priority.show_level();
}
}
public static void Main(String[] args)
{
//Make object of Binary Tree
BinaryTree tree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
1
/    \
3       2
/       / \
4       9   6
/  \    / \    \
7    8  2   4    10
*/
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(3);
tree.root.right = new TreeNode(2);
tree.root.right.right = new TreeNode(6);
tree.root.right.left = new TreeNode(9);
tree.root.right.left.left = new TreeNode(2);
tree.root.left.left = new TreeNode(4);
tree.root.left.left.left = new TreeNode(7);
tree.root.left.left.right = new TreeNode(8);
tree.root.right.left.right = new TreeNode(4);
tree.root.right.right.right = new TreeNode(10);
//level element in sorted order
tree.sorted_level();
}
}``````

#### Output

``````Sorted Level
[ 1 ]
[ 2 3 ]
[ 4 6 9 ]
[ 2 4 7 8 10 ]``````
``````<?php
/*
Php program
Print binary tree level in sorted order
*/

//Binary Tree node
class TreeNode
{
public \$data;
public \$left;
public \$right;

function __construct(\$data)
{
//set node value
\$this->data = \$data;
\$this->left = null;
\$this->right = null;
}
}
// Queue Node
class QueueNode
{
public \$element;
public \$next;
public \$level;

function __construct(\$element, \$level)
{
\$this->element = \$element;
\$this->next = null;
\$this->level = \$level;
}
}
//Define custom queue class
class MyQueue
{
public \$front;
public \$tail;

function __construct()
{
\$this->front = null;
\$this->tail = null;
}
//Add a new node at last of queue
public	function enqueue(\$element, \$level)
{
\$new_node = new QueueNode(\$element, \$level);
if (\$this->front == null)
{
//When first node of queue
\$this->front = \$new_node;
}
else
{
\$this->tail->next = \$new_node;
}
\$this->tail = \$new_node;
}
//Delete first node of queue
public	function dequeue()
{
if (\$this->front != null)
{
if (\$this->tail == \$this->front)
{
\$this->tail = null;
\$this->front = null;
}
else
{
\$this->front = \$this->front->next;
}
}
}
//Add a new node in sorted order
public	function sort_enqueue(\$element)
{
\$new_node = new QueueNode(\$element, 0);
if (\$this->front == null)
{
//When first node of queue
\$this->front = \$new_node;
\$this->tail = \$new_node;
}
else if (\$this->front->element->data >= \$element->data)
{
\$new_node->next = \$this->front;
\$this->front = \$new_node;
}
else if (\$this->tail->element->data <= \$element->data)
{
\$this->tail->next = \$new_node;
\$this->tail = \$new_node;
}
else
{
//When need to add node at intermediate position
\$temp = \$this->front;
//Find location to add new node
while (\$temp->next != null && \$temp->next->element->data < \$element->data)
{
\$temp = \$temp->next;
}
\$new_node->next = \$temp->next;
\$temp->next = \$new_node;
}
}
public	function is_empty()
{
if (\$this->front == null)
{
return true;
}
else
{
return false;
}
}
public	function show_level()
{
if (\$this->front == null)
{
return;
}
\$temp = null;
echo "\n[";
while (\$this->is_empty() == false)
{
\$temp = \$this->front;
echo " ". \$temp->element->data;
\$temp->element = null;
\$this->dequeue();
}
echo " ]";
}
}
class BinaryTree
{
public \$root;

function __construct()
{
//set initial tree root to null
\$this->root = null;
}
//Display Inorder view of binary tree
public	function inorder(\$node)
{
if (\$node != null)
{
// Executing left subtree
\$this->inorder(\$node->left);
//Print node value
echo "  ". \$node->data;
// Executing right subtree
\$this->inorder(\$node->right);
}
}
public	function sorted_level()
{
if (\$this->root == null)
{
echo "\n Empty Binary Tree \n";
}
else
{
//Get top node in tree
\$node = \$this->root;
//Define some useful counter variables
\$level_counter = 1;
\$node_level = 0;
//Create a normal Queue
\$queue = new MyQueue();
//Create a sorted priority Queue
\$priority = new MyQueue();
//Add first node at the level of one
\$queue->enqueue(\$node, \$level_counter);
echo "\nSorted Level  ";
//Execute loop until the queue is not empty
while (\$queue->is_empty() == false)
{
\$node = \$queue->front->element;
\$node_level = \$queue->front->level;
if (\$node->left != null)
{
\$queue->enqueue(\$node->left, \$node_level + 1);
}
if (\$node->right != null)
{
\$queue->enqueue(\$node->right, \$node_level + 1);
}
if (\$node_level != \$level_counter)
{
\$level_counter = \$queue->front->level;
\$priority->show_level();
}
\$priority->sort_enqueue(\$node);
//remove element into queue
\$queue->dequeue();
}
\$priority->show_level();
}
}
}

function main()
{
//Make object of Binary Tree
\$tree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
1
/    \
3       2
/       / \
4       9   6
/  \    / \    \
7    8  2   4    10
*/
\$tree->root = new TreeNode(1);
\$tree->root->left = new TreeNode(3);
\$tree->root->right = new TreeNode(2);
\$tree->root->right->right = new TreeNode(6);
\$tree->root->right->left = new TreeNode(9);
\$tree->root->right->left->left = new TreeNode(2);
\$tree->root->left->left = new TreeNode(4);
\$tree->root->left->left->left = new TreeNode(7);
\$tree->root->left->left->right = new TreeNode(8);
\$tree->root->right->left->right = new TreeNode(4);
\$tree->root->right->right->right = new TreeNode(10);
//level element in sorted order
\$tree->sorted_level();
}
main();``````

#### Output

``````Sorted Level
[ 1 ]
[ 2 3 ]
[ 4 6 9 ]
[ 2 4 7 8 10 ]``````
``````/*
Node Js program
Print binary tree level in sorted order
*/

//Binary Tree node
class TreeNode
{
constructor(data)
{
//set node value
this.data = data;
this.left = null;
this.right = null;
}
}
// Queue Node
class QueueNode
{
constructor(element, level)
{
this.element = element;
this.next = null;
this.level = level;
}
}
//Define custom queue class
class MyQueue
{
constructor()
{
this.front = null;
this.tail = null;
}
//Add a new node at last of queue
enqueue(element, level)
{
var new_node = new QueueNode(element, level);
if (this.front == null)
{
//When first node of queue
this.front = new_node;
}
else
{
this.tail.next = new_node;
}
this.tail = new_node;
}
//Delete first node of queue
dequeue()
{
if (this.front != null)
{
if (this.tail == this.front)
{
this.tail = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
}
}
//Add a new node in sorted order
sort_enqueue(element)
{
var new_node = new QueueNode(element, 0);
if (this.front == null)
{
//When first node of queue
this.front = new_node;
this.tail = new_node;
}
else if (this.front.element.data >= element.data)
{
new_node.next = this.front;
this.front = new_node;
}
else if (this.tail.element.data <= element.data)
{
this.tail.next = new_node;
this.tail = new_node;
}
else
{
//When need to add node at intermediate position
var temp = this.front;
//Find location to add new node
while (temp.next != null && temp.next.element.data < element.data)
{
temp = temp.next;
}
new_node.next = temp.next;
temp.next = new_node;
}
}
is_empty()
{
if (this.front == null)
{
return true;
}
else
{
return false;
}
}
show_level()
{
if (this.front == null)
{
return;
}
var temp = null;
process.stdout.write("\n[");
while (this.is_empty() == false)
{
temp = this.front;
process.stdout.write(" " + temp.element.data);
temp.element = null;
this.dequeue();
}
process.stdout.write(" ]");
}
}
class BinaryTree
{
constructor()
{
//set initial tree root to null
this.root = null;
}
//Display Inorder view of binary tree
inorder(node)
{
if (node != null)
{
// Executing left subtree
this.inorder(node.left);
//Print node value
process.stdout.write("  " + node.data);
// Executing right subtree
this.inorder(node.right);
}
}
sorted_level()
{
if (this.root == null)
{
process.stdout.write("\n Empty Binary Tree \n");
}
else
{
//Get top node in tree
var node = this.root;
//Define some useful counter variables
var level_counter = 1;
var node_level = 0;
//Create a normal Queue
var queue = new MyQueue();
//Create a sorted priority Queue
var priority = new MyQueue();
//Add first node at the level of one
queue.enqueue(node, level_counter);
process.stdout.write("\nSorted Level  ");
//Execute loop until the queue is not empty
while (queue.is_empty() == false)
{
node = queue.front.element;
node_level = queue.front.level;
if (node.left != null)
{
queue.enqueue(node.left, node_level + 1);
}
if (node.right != null)
{
queue.enqueue(node.right, node_level + 1);
}
if (node_level != level_counter)
{
level_counter = queue.front.level;
priority.show_level();
}
priority.sort_enqueue(node);
//remove element into queue
queue.dequeue();
}
priority.show_level();
}
}
}

function main()
{
//Make object of Binary Tree
var tree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
1
/    \
3       2
/       / \
4       9   6
/  \    / \    \
7    8  2   4    10
*/
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(3);
tree.root.right = new TreeNode(2);
tree.root.right.right = new TreeNode(6);
tree.root.right.left = new TreeNode(9);
tree.root.right.left.left = new TreeNode(2);
tree.root.left.left = new TreeNode(4);
tree.root.left.left.left = new TreeNode(7);
tree.root.left.left.right = new TreeNode(8);
tree.root.right.left.right = new TreeNode(4);
tree.root.right.right.right = new TreeNode(10);
//level element in sorted order
tree.sorted_level();
}
main();``````

#### Output

``````Sorted Level
[ 1 ]
[ 2 3 ]
[ 4 6 9 ]
[ 2 4 7 8 10 ]``````
``````#   Python 3 program
#   Print binary tree level in sorted order

# Binary Tree node
class TreeNode :

def __init__(self, data) :
# set node value
self.data = data
self.left = None
self.right = None

#  Queue Node
class QueueNode :

def __init__(self, element, level) :
self.element = element
self.next = None
self.level = level

# Define custom queue class
class MyQueue :

def __init__(self) :
self.front = None
self.tail = None

# Add a new node at last of queue
def enqueue(self, element, level) :
new_node = QueueNode(element, level)
if (self.front == None) :
# When first node of queue
self.front = new_node
else :
# Add node at last position
self.tail.next = new_node

self.tail = new_node

# Delete first node of queue
def dequeue(self) :
if (self.front != None) :
if (self.tail == self.front) :
self.tail = None
self.front = None
else :
self.front = self.front.next

# Add a new node in sorted order
def sort_enqueue(self, element) :
new_node = QueueNode(element, 0)
if (self.front == None) :
# When first node of queue
self.front = new_node
self.tail = new_node

elif(self.front.element.data >= element.data) :
new_node.next = self.front
self.front = new_node

elif(self.tail.element.data <= element.data) :
# Add node at last position
self.tail.next = new_node
self.tail = new_node
else :
# When need to add node at intermediate position
temp = self.front
# Find location to add new node
while (temp.next != None and temp.next.element.data < element.data) :
temp = temp.next

new_node.next = temp.next
temp.next = new_node

def is_empty(self) :
if (self.front == None) :
return True
else :
return False

def show_level(self) :
if (self.front == None) :
return

temp = None
print("\n[", end = "")
while (self.is_empty() == False) :
temp = self.front
print(" ", temp.element.data, end = "")
temp.element = None
self.dequeue()

print(" ]", end = "")

class BinaryTree :

def __init__(self) :
# set initial tree root to null
self.root = None

# Display Inorder view of binary tree
def inorder(self, node) :
if (node != None) :
#  Executing left subtree
self.inorder(node.left)
# Print node value
print("  ", node.data, end = "")
#  Executing right subtree
self.inorder(node.right)

def sorted_level(self) :
if (self.root == None) :
print("\n Empty Binary Tree \n", end = "")
else :
# Get top node in tree
node = self.root
# Define some useful counter variables
level_counter = 1
node_level = 0
# Create a normal Queue
queue = MyQueue()
# Create a sorted priority Queue
priority = MyQueue()
# Add first node at the level of one
queue.enqueue(node, level_counter)
print("\nSorted Level  ", end = "")
# Execute loop until the queue is not empty
while (queue.is_empty() == False) :
node = queue.front.element
node_level = queue.front.level
if (node.left != None) :
queue.enqueue(node.left, node_level + 1)

if (node.right != None) :
queue.enqueue(node.right, node_level + 1)

if (node_level != level_counter) :
level_counter = queue.front.level
priority.show_level()

priority.sort_enqueue(node)
# remove element into queue
queue.dequeue()

priority.show_level()

def main() :
# Make object of Binary Tree
tree = BinaryTree()
#
# 		Construct Binary Tree
# 		-----------------------
# 		            1
# 		         /    \
# 		        3       2
# 		       /       / \
# 		      4       9   6
# 		     /  \    / \    \
# 		    7    8  2   4    10
#

tree.root = TreeNode(1)
tree.root.left = TreeNode(3)
tree.root.right = TreeNode(2)
tree.root.right.right = TreeNode(6)
tree.root.right.left = TreeNode(9)
tree.root.right.left.left = TreeNode(2)
tree.root.left.left = TreeNode(4)
tree.root.left.left.left = TreeNode(7)
tree.root.left.left.right = TreeNode(8)
tree.root.right.left.right = TreeNode(4)
tree.root.right.right.right = TreeNode(10)
# level element in sorted order
tree.sorted_level()

if __name__ == "__main__": main()``````

#### Output

``````Sorted Level
[  1 ]
[  2  3 ]
[  4  6  9 ]
[  2  4  7  8  10 ]``````
``````#   Ruby program
#   Print binary tree level in sorted order

# Binary Tree node
class TreeNode
# Define the accessor and reader of class TreeNode
attr_accessor :data, :left, :right

def initialize(data)
# set node value
self.data = data
self.left = nil
self.right = nil
end

end

#  Queue Node
class QueueNode
# Define the accessor and reader of class QueueNode
attr_accessor :element, :next, :level

def initialize(element, level)
self.element = element
self.next = nil
self.level = level
end

end

# Define custom queue class
class MyQueue
# Define the accessor and reader of class MyQueue
attr_accessor :front, :tail

def initialize()
self.front = nil
self.tail = nil
end

# Add a new node at last of queue
def enqueue(element, level)
new_node = QueueNode.new(element, level)
if (self.front == nil)
# When first node of queue
self.front = new_node
else
# Add node at last position
self.tail.next = new_node
end

self.tail = new_node
end

# Delete first node of queue
def dequeue()
if (self.front != nil)
if (self.tail == self.front)
self.tail = nil
self.front = nil
else
self.front = self.front.next
end

end

end

# Add a new node in sorted order
def sort_enqueue(element)
new_node = QueueNode.new(element, 0)
if (self.front == nil)
# When first node of queue
self.front = new_node
self.tail = new_node
elsif(self.front.element.data >= element.data)
new_node.next = self.front
self.front = new_node
elsif(self.tail.element.data <= element.data)
# Add node at last position
self.tail.next = new_node
self.tail = new_node
else
# When need to add node at intermediate position
temp = self.front
# Find location to add new node
while (temp.next != nil && temp.next.element.data < element.data)
temp = temp.next
end

new_node.next = temp.next
temp.next = new_node
end

end

def is_empty()
if (self.front == nil)
return true
else
return false
end

end

def show_level()
if (self.front == nil)
return
end

temp = nil
print("\n[")
while (self.is_empty() == false)
temp = self.front
print(" ", temp.element.data)
temp.element = nil
self.dequeue()
end

print(" ]")
end

end

class BinaryTree
# Define the accessor and reader of class BinaryTree
attr_accessor :root

def initialize()
# set initial tree root to null
self.root = nil
end

# Display Inorder view of binary tree
def inorder(node)
if (node != nil)
#  Executing left subtree
self.inorder(node.left)
# Print node value
print("  ", node.data)
#  Executing right subtree
self.inorder(node.right)
end

end

def sorted_level()
if (self.root == nil)
print("\n Empty Binary Tree \n")
else
# Get top node in tree
node = self.root
# Define some useful counter variables
level_counter = 1
node_level = 0
# Create a normal Queue
queue = MyQueue.new()
# Create a sorted priority Queue
priority = MyQueue.new()
# Add first node at the level of one
queue.enqueue(node, level_counter)
print("\nSorted Level  ")
# Execute loop until the queue is not empty
while (queue.is_empty() == false)
node = queue.front.element
node_level = queue.front.level
if (node.left != nil)
queue.enqueue(node.left, node_level + 1)
end

if (node.right != nil)
queue.enqueue(node.right, node_level + 1)
end

if (node_level != level_counter)
level_counter = queue.front.level
priority.show_level()
end

priority.sort_enqueue(node)
# remove element into queue
queue.dequeue()
end

priority.show_level()
end

end

end

def main()
# Make object of Binary Tree
tree = BinaryTree.new()
#
# 		Construct Binary Tree
# 		-----------------------
# 		            1
# 		         /    \
# 		        3       2
# 		       /       / \
# 		      4       9   6
# 		     /  \    / \    \
# 		    7    8  2   4    10
#

tree.root = TreeNode.new(1)
tree.root.left = TreeNode.new(3)
tree.root.right = TreeNode.new(2)
tree.root.right.right = TreeNode.new(6)
tree.root.right.left = TreeNode.new(9)
tree.root.right.left.left = TreeNode.new(2)
tree.root.left.left = TreeNode.new(4)
tree.root.left.left.left = TreeNode.new(7)
tree.root.left.left.right = TreeNode.new(8)
tree.root.right.left.right = TreeNode.new(4)
tree.root.right.right.right = TreeNode.new(10)
# level element in sorted order
tree.sorted_level()
end

main()``````

#### Output

``````Sorted Level
[ 1 ]
[ 2 3 ]
[ 4 6 9 ]
[ 2 4 7 8 10 ]``````
``````/*
Scala program
Print binary tree level in sorted order
*/
//Binary Tree node
class TreeNode(var data: Int,
var left: TreeNode,
var right: TreeNode)
{
def this(data: Int)
{
this(data, null, null);
}
}
// Queue Node
class QueueNode(var element: TreeNode,
var next: QueueNode,
var level: Int)
{
def this(element: TreeNode, level: Int)
{
this(element, null, level);
}
}
//Define custom queue class
class MyQueue(var front: QueueNode,
var tail: QueueNode)
{
def this()
{
this(null, null);
}
//Add a new node at last of queue
def enqueue(element: TreeNode, level: Int): Unit = {
var new_node: QueueNode = new QueueNode(element, level);
if (this.front == null)
{
//When first node of queue
this.front = new_node;
}
else
{
this.tail.next = new_node;
}
this.tail = new_node;
}
//Delete first node of queue
def dequeue(): Unit = {
if (this.front != null)
{
if (this.tail == this.front)
{
this.tail = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
}
}
//Add a new node in sorted order
def sort_enqueue(element: TreeNode): Unit = {
var new_node: QueueNode = new QueueNode(element, 0);
if (this.front == null)
{
//When first node of queue
this.front = new_node;
this.tail = new_node;
}
else if (this.front.element.data >= element.data)
{
new_node.next = this.front;
this.front = new_node;
}
else if (this.tail.element.data <= element.data)
{
this.tail.next = new_node;
this.tail = new_node;
}
else
{
//When need to add node at intermediate position
var temp: QueueNode = this.front;
//Find location to add new node
while (temp.next != null && temp.next.element.data < element.data)
{
temp = temp.next;
}
new_node.next = temp.next;
temp.next = new_node;
}
}
def is_empty(): Boolean = {
if (this.front == null)
{
return true;
}
else
{
return false;
}
}
def show_level(): Unit = {
if (this.front == null)
{
return;
}
var temp: QueueNode = null;
print("\n[");
while (this.is_empty() == false)
{
temp = this.front;
print(" " + temp.element.data);
temp.element = null;
this.dequeue();
}
print(" ]");
}
}
class BinaryTree(var root: TreeNode)
{
def this()
{
this(null);
}
//Display Inorder view of binary tree
def inorder(node: TreeNode): Unit = {
if (node != null)
{
// Executing left subtree
this.inorder(node.left);
//Print node value
print("  " + node.data);
// Executing right subtree
this.inorder(node.right);
}
}
def sorted_level(): Unit = {
if (this.root == null)
{
print("\n Empty Binary Tree \n");
}
else
{
//Get top node in tree
var node: TreeNode = this.root;
//Define some useful counter variables
var level_counter: Int = 1;
var node_level: Int = 0;
//Create a normal Queue
var queue: MyQueue = new MyQueue();
//Create a sorted priority Queue
var priority: MyQueue = new MyQueue();
//Add first node at the level of one
queue.enqueue(node, level_counter);
print("\nSorted Level  ");
//Execute loop until the queue is not empty
while (queue.is_empty() == false)
{
node = queue.front.element;
node_level = queue.front.level;
if (node.left != null)
{
queue.enqueue(node.left, node_level + 1);
}
if (node.right != null)
{
queue.enqueue(node.right, node_level + 1);
}
if (node_level != level_counter)
{
level_counter = queue.front.level;
priority.show_level();
}
priority.sort_enqueue(node);
//remove element into queue
queue.dequeue();
}
priority.show_level();
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
//Make object of Binary Tree
var tree: BinaryTree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
1
/    \
3       2
/       / \
4       9   6
/  \    / \    \
7    8  2   4    10
*/
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(3);
tree.root.right = new TreeNode(2);
tree.root.right.right = new TreeNode(6);
tree.root.right.left = new TreeNode(9);
tree.root.right.left.left = new TreeNode(2);
tree.root.left.left = new TreeNode(4);
tree.root.left.left.left = new TreeNode(7);
tree.root.left.left.right = new TreeNode(8);
tree.root.right.left.right = new TreeNode(4);
tree.root.right.right.right = new TreeNode(10);
//level element in sorted order
tree.sorted_level();
}
}``````

#### Output

``````Sorted Level
[ 1 ]
[ 2 3 ]
[ 4 6 9 ]
[ 2 4 7 8 10 ]``````
``````/*
Swift 4 program
Print binary tree level in sorted order
*/

//Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode? ;
var right: TreeNode? ;
init(_ data: Int)
{
//set node value
self.data = data;
self.left = nil;
self.right = nil;
}
}
// Queue Node
class QueueNode
{
var element: TreeNode? ;
var next: QueueNode? ;
var level: Int;
init(_ element: TreeNode? , _ level : Int)
{
self.element = element;
self.next = nil;
self.level = level;
}
}
//Define custom queue class
class MyQueue
{
var front: QueueNode? ;
var tail: QueueNode? ;
init()
{
self.front = nil;
self.tail = nil;
}
//Add a new node at last of queue
func enqueue(_ element: TreeNode? , _ level : Int)
{
let new_node: QueueNode? = QueueNode(element, level);
if (self.front == nil)
{
//When first node of queue
self.front = new_node;
}
else
{
self.tail!.next = new_node;
}
self.tail = new_node;
}
//Delete first node of queue
func dequeue()
{
if (self.front != nil)
{
if (self.tail === self.front)
{
self.tail = nil;
self.front = nil;
}
else
{
self.front = self.front!.next;
}
}
}
//Add a new node in sorted order
func sort_enqueue(_ element: TreeNode? )
{
let new_node: QueueNode? = QueueNode(element, 0);
if (self.front == nil)
{
//When first node of queue
self.front = new_node;
self.tail = new_node;
}
else if (self.front!.element!.data >= element!.data)
{
new_node!.next = self.front;
self.front = new_node;
}
else if (self.tail!.element!.data <= element!.data)
{
self.tail!.next = new_node;
self.tail = new_node;
}
else
{
//When need to add node at intermediate position
var temp: QueueNode? = self.front;
//Find location to add new node
while (temp!.next != nil && temp!.next!.element!.data < element!.data)
{
temp = temp!.next;
}
new_node!.next = temp!.next;
temp!.next = new_node;
}
}
func is_empty() -> Bool
{
if (self.front == nil)
{
return true;
}
else
{
return false;
}
}
func show_level()
{
if (self.front == nil)
{
return;
}
var temp: QueueNode? = nil;
print("\n[", terminator: "");
while (self.is_empty() == false)
{
temp = self.front;
print(" ", temp!.element!.data, terminator: "");
temp!.element = nil;
self.dequeue();
}
print(" ]", terminator: "");
}
}
class BinaryTree
{
var root: TreeNode? ;
init()
{
//set initial tree root to null
self.root = nil;
}
//Display Inorder view of binary tree
func inorder(_ node: TreeNode? )
{
if (node != nil)
{
// Executing left subtree
self.inorder(node!.left);
//Print node value
print("  ", node!.data, terminator: "");
// Executing right subtree
self.inorder(node!.right);
}
}
func sorted_level()
{
if (self.root == nil)
{
print("\n Empty Binary Tree \n", terminator: "");
}
else
{
//Get top node in tree
var node: TreeNode? = self.root;
//Define some useful counter variables
var level_counter: Int = 1;
var node_level: Int = 0;
//Create a normal Queue
let queue: MyQueue = MyQueue();
//Create a sorted priority Queue
let priority: MyQueue = MyQueue();
//Add first node at the level of one
queue.enqueue(node, level_counter);
print("\nSorted Level  ", terminator: "");
//Execute loop until the queue is not empty
while (queue.is_empty() == false)
{
node = queue.front!.element;
node_level = queue.front!.level;
if (node!.left != nil)
{
queue.enqueue(node!.left, node_level + 1);
}
if (node!.right != nil)
{
queue.enqueue(node!.right, node_level + 1);
}
if (node_level != level_counter)
{
level_counter = queue.front!.level;
priority.show_level();
}
priority.sort_enqueue(node);
//remove element into queue
queue.dequeue();
}
priority.show_level();
}
}
}
func main()
{
//Make object of Binary Tree
let tree: BinaryTree = BinaryTree();
/*
Construct Binary Tree
-----------------------
1
/    \
3       2
/       / \
4       9   6
/  \    / \    \
7    8  2   4    10
*/
tree.root = TreeNode(1);
tree.root!.left = TreeNode(3);
tree.root!.right = TreeNode(2);
tree.root!.right!.right = TreeNode(6);
tree.root!.right!.left = TreeNode(9);
tree.root!.right!.left!.left = TreeNode(2);
tree.root!.left!.left = TreeNode(4);
tree.root!.left!.left!.left = TreeNode(7);
tree.root!.left!.left!.right = TreeNode(8);
tree.root!.right!.left!.right = TreeNode(4);
tree.root!.right!.right!.right = TreeNode(10);
//level element in sorted order
tree.sorted_level();
}
main();``````

#### Output

``````Sorted Level
[  1 ]
[  2  3 ]
[  4  6  9 ]
[  2  4  7  8  10 ]``````

## Resultant Output Explanation

The output shows the nodes at each level of the binary tree in sorted order. For each level, the nodes are sorted in ascending order. The first level contains only the root node (1), which is already sorted. The second level contains nodes 2 and 3 in sorted order. The third level contains nodes 4, 6, and 9 in sorted order. The fourth and final level contains nodes 2, 4, 7, 8, and 10 in sorted order.

## Time Complexity

The time complexity of the algorithm is O(NlogN), where N is the number of nodes in the binary tree. This is because, for each level of the tree, we need to perform sorting on a custom queue with at most N elements, and sorting N elements takes O(NlogN) time complexity. Since the BFS traversal itself takes O(N) time, the overall time complexity is dominated by the sorting operation at each level, resulting in O(NlogN) time complexity.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post