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

//Add element in sorted order
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)
        {
            //Add node at begining
            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)
            {
                //Add new left child node
                tail->next = enqueue(node->left);

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

                tail = tail->next;
            }
            if (node->right != NULL)
            {
                //Add new right child node
                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
    {
        printf("Empty Linked List\n");
    }
}
int main()
{
    struct Node *root = NULL;
    /*  
    Construct Binary Tree
    -----------------------
                1
             /    \
            3       2
           /       / \
          4       9   6
         /  \    / \    \
        7    8  2   4    10
    */
    //Add node
    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
		{
			//Add node at last position
			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)
		{
			//Add node at beginning
			new_node.next = this.front;
			this.front = new_node;
		}
		else if (this.tail.element.data <= element.data)
		{
			//Add node at last position
			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)
				{
					//Add left node
					queue.enqueue(node.left, node_level + 1);
				}
				if (node.right != null)
				{
					//Add right node
					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
		*/
		//Add node
		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
		{
			//Add node at last position
			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)
		{
			//Add node at beginning
			new_node->next = this->front;
			this->front = new_node;
		}
		else if (this->tail->element->data <= element->data)
		{
			//Add node at last position
			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)
				{
					//Add left node
					queue->enqueue(node->left, node_level + 1);
				}
				if (node->right != NULL)
				{
					//Add right node
					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
			*/
	//Add node
	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
		{
			//Add node at last position
			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)
		{
			//Add node at beginning
			new_node.next = this.front;
			this.front = new_node;
		}
		else if (this.tail.element.data <= element.data)
		{
			//Add node at last position
			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)
				{
					//Add left node
					queue.enqueue(node.left, node_level + 1);
				}
				if (node.right != null)
				{
					//Add right node
					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
				*/
		//Add node
		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
		{
			//Add node at last position
			$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)
		{
			//Add node at beginning
			$new_node->next = $this->front;
			$this->front = $new_node;
		}
		else if ($this->tail->element->data <= $element->data)
		{
			//Add node at last position
			$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)
				{
					//Add left node
					$queue->enqueue($node->left, $node_level + 1);
				}
				if ($node->right != null)
				{
					//Add right node
					$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
			*/
	//Add node
	$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
		{
			//Add node at last position
			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)
		{
			//Add node at beginning
			new_node.next = this.front;
			this.front = new_node;
		}
		else if (this.tail.element.data <= element.data)
		{
			//Add node at last position
			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)
				{
					//Add left node
					queue.enqueue(node.left, node_level + 1);
				}
				if (node.right != null)
				{
					//Add right node
					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
			*/
	//Add node
	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) :
			# Add node at beginning
			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) :
					# Add left node
					queue.enqueue(node.left, node_level + 1)
				
				if (node.right != None) :
					# Add right node
					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
	# 		
	
	# Add node
	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_reader :data, :left, :right
	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_reader :element, :next, :level
	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_reader :front, :tail
	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) 
			# Add node at beginning
			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_reader :root
	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) 
					# Add left node
					queue.enqueue(node.left, node_level + 1)
				end

				if (node.right != nil) 
					# Add right node
					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
	# 		
	
	# Add node
	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
		{
			//Add node at last position
			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)
		{
			//Add node at beginning
			new_node.next = this.front;
			this.front = new_node;
		}
		else if (this.tail.element.data <= element.data)
		{
			//Add node at last position
			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)
				{
					//Add left node
					queue.enqueue(node.left, node_level + 1);
				}
				if (node.right != null)
				{
					//Add right node
					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
				*/
		//Add node
		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
		{
			//Add node at last position
			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)
		{
			//Add node at beginning
			new_node!.next = self.front;
			self.front = new_node;
		}
		else if (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
			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)
				{
					//Add left node
					queue.enqueue(node!.left, node_level + 1);
				}
				if (node!.right != nil)
				{
					//Add right node
					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
			*/
	//Add node
	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.

New Comment