Skip to main content

Tree sort

Tree sort is a sorting algorithm that works by building a binary search tree from the elements to be sorted, and then traversing the tree in-order to obtain the sorted sequence. The algorithm was first proposed by J. W. S. Williams in 1964.

Here is an overview of how the tree sort algorithm works:

  1. Insert all the elements to be sorted into a binary search tree. Each element is inserted in such a way that it satisfies the binary search tree property, which means that the left child of a node is always less than its parent, and the right child is always greater than or equal to its parent.

  2. Traverse the binary search tree in-order, which means visiting the left subtree first, then the root, and then the right subtree. This traversal will visit all the nodes of the tree in sorted order, and hence the output will be the sorted sequence of elements.

  3. Remove the elements from the binary search tree as they are visited during the in-order traversal.

The time complexity of tree sort depends on the shape of the binary search tree, which in turn depends on the order in which the elements are inserted. In the best case, the binary search tree is balanced, and the time complexity is O(n log n). In the worst case, the binary search tree can degenerate into a linear chain, and the time complexity becomes O(n^2). However, the average case time complexity is O(n log n) for random input data.

Here given code implementation process.

// C Program 
// Sort array elements by using tree sort
#include <stdio.h>

#include <stdlib.h>
 //Structure of Binary Search Tree node
struct Node
{
	int data;
	struct Node *left, *right;
};
//Adding a new node in binary search tree
void add(struct Node **root, int data)
{
	//Create a dynamic node of binary search tree 
	struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));
	if (new_node != NULL)
	{
		//Set data and pointer values
		new_node->data = data;
		new_node->left = NULL; //Initially node left-pointer is NULL
		new_node->right = NULL; //Initially node right-pointer is NULL
		if ( *root == NULL)
		{
			//When adds a first node in binary tree
			*root = new_node;
		}
		else
		{
			struct Node *find = *root;
			//add new node to proper position
			while (find != NULL)
			{
				if (find->data >= data)
				{
					if (find->left == NULL)
					{
						find->left = new_node;
						break;
					}
					else
					{
						//visit left sub-tree
						find = find->left;
					}
				}
				else
				{
					if (find->right == NULL)
					{
						find->right = new_node;
						break;
					}
					else
					{
						//visit right sub-tree
						find = find->right;
					}
				}
			}
		}
	}
	else
	{
		printf("Memory Overflow\n");
		exit(0); //Terminate program execution
	}
}
//Function which is display arr elements
void display(int arr[], int size)
{
	for (int i = 0; i < size; ++i)
	{
		printf("  %d", arr[i]);
	}
	printf("\n");
}
//Add sorted order elements into array
struct Node *inorder_sort(struct Node *root, int arr[], int *location)
{
	if (root != NULL)
	{
		root->left = inorder_sort(root->left, arr, location);
		//insert tree elements into array
		arr[ *location] = root->data;*location = *location + 1;
		root->right = inorder_sort(root->right, arr, location);
		//Safely remove tree element
		if (root->left == NULL && root->right == NULL)
		{
			//When leaf node found then remove current element
			free(root);
			root = NULL;
		}
	}
	return root;
}
//Executing the tree sort in given array
void tree_sort(int arr[], int size)
{
	int i = 0;
	struct Node *root = NULL;
	for (i = 0; i < size; ++i)
	{
		add( & root, arr[i]);
	}
	i = 0;
	root = inorder_sort(root, arr, & i);
}
int main()
{
	//Define an array of integers
	int arr1[] = {
		3 , 6 , 2 , 5 , -7 , 2 , 1 , 4 , 7 , 8 , 2
	};
	//Get the size of arr
	int size = sizeof(arr1) / sizeof(arr1[0]);
	//Before sort
	printf("\n  Before Sort  :\n");
	display(arr1, size);
	//Sort element
	tree_sort(arr1, size);
	//After sort
	printf("\n  After Sort  :\n");
	display(arr1, size);
	int arr2[] = {
		8 , 2 , 9 , -6 , 3 , 2 , 31 , 41 , 2 , 1 , 67 , 32
	};
	//Get the size of arr
	size = sizeof(arr2) / sizeof(arr2[0]);
	//Before sort
	printf("\n  Before Sort  :\n");
	display(arr2, size);
	//Sort element
	tree_sort(arr2, size);
	//After sort
	printf("\n  After Sort  :\n");
	display(arr2, size);
	return 0;
}

Output

  Before Sort  :
  3  6  2  5  -7  2  1  4  7  8  2

  After Sort  :
  -7  1  2  2  2  3  4  5  6  7  8

  Before Sort  :
  8  2  9  -6  3  2  31  41  2  1  67  32

  After Sort  :
  -6  1  2  2  2  3  8  9  31  32  41  67
/*
	Java Program
	Sort array elements by using tree sort
*/
//Binary Search Tree Node
class Node
{
	// Data value 
	public int data;
	// Indicates left and right subtree
	public Node left;
	public Node right;
	public Node(int data)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class MySort
{
	public Node root;
	public int location;
	public MySort()
	{
		this.root = null;
		this.location = 0;
	}
	//Function which is display arr elements
	public void display(int[] arr, int size)
	{
		for (int i = 0; i < size; ++i)
		{
			System.out.print(" " + arr[i]);
		}
		System.out.print("\n");
	}
	//insert a node in BST
	public void add(int data)
	{
		//Create a dynamic node of binary search tree 
		Node new_node = new Node(data);
		if (new_node != null)
		{
			if (this.root == null)
			{
				//When adds a first node in tree
				this.root = new_node;
			}
			else
			{
				Node find = this.root;
				//add new node to proper position
				while (find != null)
				{
					if (find.data >= data)
					{
						if (find.left == null)
						{
							find.left = new_node;
							return;
						}
						else
						{
							//visit left sub-tree
							find = find.left;
						}
					}
					else
					{
						if (find.right == null)
						{
							find.right = new_node;
							return;
						}
						else
						{
							//visit right sub-tree
							find = find.right;
						}
					}
				}
			}
		}
		else
		{
			System.out.print("\nMemory Overflow\n");
		}
	}
	//Add sorted order elements into array
	public Node inorder_sort(Node head, int[] arr)
	{
		if (head != null)
		{
			head.left = inorder_sort(head.left, arr);
			//insert tree elements into array
			arr[location] = head.data;
			this.location = this.location + 1;
			head.right = inorder_sort(head.right, arr);
			//Safely remove tree element
			if (head.left == null && head.right == null)
			{
				//When leaf node found then remove current element
				head = null;
			}
		}
		return head;
	}
	//Executing the tree sort in given array
	public void tree_sort(int[] arr, int size)
	{
		int i = 0;
		for (i = 0; i < size; ++i)
		{
			add(arr[i]);
		}
		this.location = 0;
		this.root = inorder_sort(root, arr);
	}
	public static void main(String[] args)
	{
		MySort obj = new MySort();
		//Define an array of integers
		int[] arr1 = {
			3,
			6,
			2,
			5,
			-7,
			2,
			1,
			4,
			7,
			8,
			2
		};
		//Get the size of arr
		int size = arr1.length;
		System.out.print("\n Before Sort :\n");
		obj.display(arr1, size);
		//Sort element
		obj.tree_sort(arr1, size);
		System.out.print("\n After Sort :\n");
		obj.display(arr1, size);
		int[] arr2 = {
			8,
			2,
			9,
			-6,
			3,
			2,
			31,
			41,
			2,
			1,
			67,
			32
		};
		//Get the size of arr
		size = arr2.length;
		System.out.print("\n Before Sort :\n");
		obj.display(arr2, size);
		//Sort element
		obj.tree_sort(arr2, size);
		System.out.print("\n After Sort :\n");
		obj.display(arr2, size);
	}
}

Output

 Before Sort :
 3 6 2 5 -7 2 1 4 7 8 2

 After Sort :
 -7 1 2 2 2 3 4 5 6 7 8

 Before Sort :
 8 2 9 -6 3 2 31 41 2 1 67 32

 After Sort :
 -6 1 2 2 2 3 8 9 31 32 41 67
//Include header file
#include <iostream>

using namespace std;
/*
	C++ Program
	Sort array elements by using tree sort
*/
//Binary Search Tree Node
class Node
{
	public:
	// Data value 
	int data;
	// Indicates left and right subtree
	Node * left;
	Node * right;
	Node(int data)
	{
		this->data = data;
		this->left = NULL;
		this->right = NULL;
	}
};
class MySort
{
	public: Node * root;
	int location;
	MySort()
	{
		this->root = NULL;
		this->location = 0;
	}
	//Function which is display arr elements
	void display(int arr[], int size)
	{
		for (int i = 0; i < size; ++i)
		{
			cout << " " << arr[i];
		}
		cout << "\n";
	}
	//insert a node in BST
	void add(int data)
	{
		//Create a dynamic node of binary search tree 
		Node * new_node = new Node(data);
		if (new_node != NULL)
		{
			if (this->root == NULL)
			{
				//When adds a first node in tree
				this->root = new_node;
			}
			else
			{
				Node * find = this->root;
				//add new node to proper position
				while (find != NULL)
				{
					if (find->data >= data)
					{
						if (find->left == NULL)
						{
							find->left = new_node;
							return;
						}
						else
						{
							//visit left sub-tree
							find = find->left;
						}
					}
					else
					{
						if (find->right == NULL)
						{
							find->right = new_node;
							return;
						}
						else
						{
							//visit right sub-tree
							find = find->right;
						}
					}
				}
			}
		}
		else
		{
			cout << "\nMemory Overflow\n";
		}
	}
	//Add sorted order elements into array
	Node * inorder_sort(Node * head, int arr[])
	{
		if (head != NULL)
		{
			head->left = this->inorder_sort(head->left, arr);
			//insert tree elements into array
			arr[this->location] = head->data;
			this->location = this->location + 1;
			head->right = this->inorder_sort(head->right, arr);
			//Safely remove tree element
			if (head->left == NULL && head->right == NULL)
			{
				//When leaf node found then remove current element
				head = NULL;
			}
		}
		return head;
	}
	//Executing the tree sort in given array
	void tree_sort(int arr[], int size)
	{
		int i = 0;
		for (i = 0; i < size; ++i)
		{
			this->add(arr[i]);
		}
		this->location = 0;
		this->root = this->inorder_sort(this->root, arr);
	}
};
int main()
{
	MySort obj = MySort();
	int arr1[] = {
		3 , 6 , 2 , 5 , -7 , 2 , 1 , 4 , 7 , 8 , 2
	};
	//Get the size of arr
	int size = sizeof(arr1) / sizeof(arr1[0]);
	cout << "\n Before Sort :\n";
	obj.display(arr1, size);
	//Sort element
	obj.tree_sort(arr1, size);
	cout << "\n After Sort :\n";
	obj.display(arr1, size);
	int arr2[] = {
		8 , 2 , 9 , -6 , 3 , 2 , 31 , 41 , 2 , 1 , 67 , 32
	};
	//Get the size of arr
	size = sizeof(arr2) / sizeof(arr2[0]);
	cout << "\n Before Sort :\n";
	obj.display(arr2, size);
	//Sort element
	obj.tree_sort(arr2, size);
	cout << "\n After Sort :\n";
	obj.display(arr2, size);
	return 0;
}

Output

 Before Sort :
 3 6 2 5 -7 2 1 4 7 8 2

 After Sort :
 -7 1 2 2 2 3 4 5 6 7 8

 Before Sort :
 8 2 9 -6 3 2 31 41 2 1 67 32

 After Sort :
 -6 1 2 2 2 3 8 9 31 32 41 67
//Include namespace system
using System;
/*
	C# Program
	Sort array elements by using tree sort
*/
//Binary Search Tree Node
class Node
{
	// Data value 
	public int data;
	// Indicates left and right subtree
	public Node left;
	public Node right;
	public Node(int data)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class MySort
{
	public Node root;
	public int location;
	public MySort()
	{
		this.root = null;
		this.location = 0;
	}
	//Function which is display arr elements
	public void display(int[] arr, int size)
	{
		for (int i = 0; i < size; ++i)
		{
			Console.Write(" " + arr[i]);
		}
		Console.Write("\n");
	}
	//insert a node in BST
	public void add(int data)
	{
		//Create a dynamic node of binary search tree 
		Node new_node = new Node(data);
		if (new_node != null)
		{
			if (this.root == null)
			{
				//When adds a first node in tree
				this.root = new_node;
			}
			else
			{
				Node find = this.root;
				//add new node to proper position
				while (find != null)
				{
					if (find.data >= data)
					{
						if (find.left == null)
						{
							find.left = new_node;
							return;
						}
						else
						{
							//visit left sub-tree
							find = find.left;
						}
					}
					else
					{
						if (find.right == null)
						{
							find.right = new_node;
							return;
						}
						else
						{
							//visit right sub-tree
							find = find.right;
						}
					}
				}
			}
		}
		else
		{
			Console.Write("\nMemory Overflow\n");
		}
	}
	//Add sorted order elements into array
	public Node inorder_sort(Node head, int[] arr)
	{
		if (head != null)
		{
			head.left = inorder_sort(head.left, arr);
			//insert tree elements into array
			arr[location] = head.data;
			this.location = this.location + 1;
			head.right = inorder_sort(head.right, arr);
			//Safely remove tree element
			if (head.left == null && head.right == null)
			{
				//When leaf node found then remove current element
				head = null;
			}
		}
		return head;
	}
	//Executing the tree sort in given array
	public void tree_sort(int[] arr, int size)
	{
		int i = 0;
		for (i = 0; i < size; ++i)
		{
			add(arr[i]);
		}
		this.location = 0;
		this.root = inorder_sort(root, arr);
	}
	public static void Main(String[] args)
	{
		MySort obj = new MySort();
		int[] arr1 = {
			3 , 6 , 2 , 5 , -7 , 2 , 1 , 4 , 7 , 8 , 2
		};
		//Get the size of arr
		int size = arr1.Length;
		Console.Write("\n Before Sort :\n");
		obj.display(arr1, size);
		//Sort element
		obj.tree_sort(arr1, size);
		Console.Write("\n After Sort :\n");
		obj.display(arr1, size);
		int[] arr2 = {
			8 , 2 , 9 , -6 , 3 , 2 , 31 , 41 , 2 , 1 , 67 , 32
		};
		//Get the size of arr
		size = arr2.Length;
		Console.Write("\n Before Sort :\n");
		obj.display(arr2, size);
		//Sort element
		obj.tree_sort(arr2, size);
		Console.Write("\n After Sort :\n");
		obj.display(arr2, size);
	}
}

Output

 Before Sort :
 3 6 2 5 -7 2 1 4 7 8 2

 After Sort :
 -7 1 2 2 2 3 4 5 6 7 8

 Before Sort :
 8 2 9 -6 3 2 31 41 2 1 67 32

 After Sort :
 -6 1 2 2 2 3 8 9 31 32 41 67
<?php
/*
	Php Program
	Sort array elements by using tree sort
*/
//Binary Search Tree Node
class Node
{
	// Data value 
	public $data;
	// Indicates left and right subtree
	public $left;
	public $right;

	function __construct($data)
	{
		$this->data = $data;
		$this->left = null;
		$this->right = null;
	}
}
class MySort
{
	public $root;
	public $location;

	function __construct()
	{
		$this->root = null;
		$this->location = 0;
	}
	//Function which is display arr elements
	public	function display($arr, $size)
	{
		for ($i = 0; $i < $size; ++$i)
		{
			echo " ". $arr[$i];
		}
		echo "\n";
	}
	//insert a node in BST
	public	function add($data)
	{
		//Create a dynamic node of binary search tree 
		$new_node = new Node($data);
		if ($new_node != null)
		{
			if ($this->root == null)
			{
				//When adds a first node in tree
				$this->root = $new_node;
			}
			else
			{
				$find = $this->root;
				//add new node to proper position
				while ($find != null)
				{
					if ($find->data >= $data)
					{
						if ($find->left == null)
						{
							$find->left = $new_node;
							return;
						}
						else
						{
							//visit left sub-tree
							$find = $find->left;
						}
					}
					else
					{
						if ($find->right == null)
						{
							$find->right = $new_node;
							return;
						}
						else
						{
							//visit right sub-tree
							$find = $find->right;
						}
					}
				}
			}
		}
		else
		{
			echo "\nMemory Overflow\n";
		}
	}
	//Add sorted order elements into array
	public	function inorder_sort($head, & $arr)
	{
		if ($head != null)
		{
			$head->left = $this->inorder_sort($head->left, $arr);
			//insert tree elements into array
			$arr[$this->location] = $head->data;
			$this->location = $this->location + 1;
			$head->right = $this->inorder_sort($head->right, $arr);
			//Safely remove tree element
			if ($head->left == null && $head->right == null)
			{
				//When leaf node found then remove current element
				$head = null;
			}
		}
		return $head;
	}
	//Executing the tree sort in given array
	public	function tree_sort( & $arr, $size)
	{
		$i = 0;
		for ($i = 0; $i < $size; ++$i)
		{
			$this->add($arr[$i]);
		}
		$this->location = 0;
		$this->root = $this->inorder_sort($this->root, $arr);
	}
}

function main()
{
	$obj = new MySort();
	//Define an array of integers
	$arr1 = array(3, 6, 2, 5, -7, 2, 1, 4, 7, 8, 2);
	//Get the size of arr
	$size = count($arr1);
	echo "\n Before Sort :\n";
	$obj->display($arr1, $size);
	//Sort element
	$obj->tree_sort($arr1, $size);
	echo "\n After Sort :\n";
	$obj->display($arr1, $size);
	$arr2 = array(8, 2, 9, -6, 3, 2, 31, 41, 2, 1, 67, 32);
	//Get the size of arr
	$size = count($arr2);
	echo "\n Before Sort :\n";
	$obj->display($arr2, $size);
	//Sort element
	$obj->tree_sort($arr2, $size);
	echo "\n After Sort :\n";
	$obj->display($arr2, $size);
}
main();

Output

 Before Sort :
 3 6 2 5 -7 2 1 4 7 8 2

 After Sort :
 -7 1 2 2 2 3 4 5 6 7 8

 Before Sort :
 8 2 9 -6 3 2 31 41 2 1 67 32

 After Sort :
 -6 1 2 2 2 3 8 9 31 32 41 67
/*
	Node Js Program
	Sort array elements by using tree sort
*/
//Binary Search Tree Node
class Node
{
	// Data value 
	// Indicates left and right subtree
	constructor(data)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class MySort
{
	constructor()
	{
		this.root = null;
		this.location = 0;
	}
	//Function which is display arr elements
	display(arr, size)
	{
		for (var i = 0; i < size; ++i)
		{
			process.stdout.write(" " + arr[i]);
		}
		process.stdout.write("\n");
	}
	//insert a node in BST
	add(data)
	{
		//Create a dynamic node of binary search tree 
		var new_node = new Node(data);
		if (new_node != null)
		{
			if (this.root == null)
			{
				//When adds a first node in tree
				this.root = new_node;
			}
			else
			{
				var find = this.root;
				//add new node to proper position
				while (find != null)
				{
					if (find.data >= data)
					{
						if (find.left == null)
						{
							find.left = new_node;
							return;
						}
						else
						{
							//visit left sub-tree
							find = find.left;
						}
					}
					else
					{
						if (find.right == null)
						{
							find.right = new_node;
							return;
						}
						else
						{
							//visit right sub-tree
							find = find.right;
						}
					}
				}
			}
		}
		else
		{
			process.stdout.write("\nMemory Overflow\n");
		}
	}
	//Add sorted order elements into array
	inorder_sort(head, arr)
	{
		if (head != null)
		{
			head.left = this.inorder_sort(head.left, arr);
			//insert tree elements into array
			arr[this.location] = head.data;
			this.location = this.location + 1;
			head.right = this.inorder_sort(head.right, arr);
			//Safely remove tree element
			if (head.left == null && head.right == null)
			{
				//When leaf node found then remove current element
				head = null;
			}
		}
		return head;
	}
	//Executing the tree sort in given array
	tree_sort(arr, size)
	{
		var i = 0;
		for (i = 0; i < size; ++i)
		{
			this.add(arr[i]);
		}
		this.location = 0;
		this.root = this.inorder_sort(this.root, arr);
	}
}

function main()
{
	var obj = new MySort();
	//Define an array of integers
	var arr1 = [3, 6, 2, 5, -7, 2, 1, 4, 7, 8, 2];
	//Get the size of arr
	var size = arr1.length;
	process.stdout.write("\n Before Sort :\n");
	obj.display(arr1, size);
	//Sort element
	obj.tree_sort(arr1, size);
	process.stdout.write("\n After Sort :\n");
	obj.display(arr1, size);
	var arr2 = [8, 2, 9, -6, 3, 2, 31, 41, 2, 1, 67, 32];
	//Get the size of arr
	size = arr2.length;
	process.stdout.write("\n Before Sort :\n");
	obj.display(arr2, size);
	//Sort element
	obj.tree_sort(arr2, size);
	process.stdout.write("\n After Sort :\n");
	obj.display(arr2, size);
}
main();

Output

 Before Sort :
 3 6 2 5 -7 2 1 4 7 8 2

 After Sort :
 -7 1 2 2 2 3 4 5 6 7 8

 Before Sort :
 8 2 9 -6 3 2 31 41 2 1 67 32

 After Sort :
 -6 1 2 2 2 3 8 9 31 32 41 67
# 	Python 3 Program
# 	Sort array elements by using tree sort

# Binary Search Tree Node
class Node :
	#  Data value 
	
	#  Indicates left and right subtree
	
	def __init__(self, data) :
		self.data = data
		self.left = None
		self.right = None
	

class MySort :
	
	def __init__(self) :
		self.root = None
		self.location = 0
	
	# Function which is display arr elements
	def display(self, arr, size) :
		i = 0
		while (i < size) :
			print(" ", arr[i], end = "")
			i += 1
		
		print("\n", end = "")
	
	# insert a node in BST
	def add(self, data) :
		# Create a dynamic node of binary search tree 
		new_node = Node(data)
		if (new_node != None) :
			if (self.root == None) :
				# When adds a first node in tree
				self.root = new_node
			else :
				find = self.root
				# add new node to proper position
				while (find != None) :
					if (find.data >= data) :
						if (find.left == None) :
							find.left = new_node
							return
						else :
							# visit left sub-tree
							find = find.left
						
					else :
						if (find.right == None) :
							find.right = new_node
							return
						else :
							# visit right sub-tree
							find = find.right
						
					
				
			
		else :
			print("\nMemory Overflow\n", end = "")
		
	
	# Add sorted order elements into array
	def inorder_sort(self, head, arr) :
		if (head != None) :
			head.left = self.inorder_sort(head.left, arr)
			# insert tree elements into array
			arr[self.location] = head.data
			self.location = self.location + 1
			head.right = self.inorder_sort(head.right, arr)
			# Safely remove tree element
			if (head.left == None and head.right == None) :
				# When leaf node found then remove current element
				head = None
			
		
		return head
	
	# Executing the tree sort in given array
	def tree_sort(self, arr, size) :
		i = 0
		i = 0
		while (i < size) :
			self.add(arr[i])
			i += 1
		
		self.location = 0
		self.root = self.inorder_sort(self.root, arr)
	

def main() :
	obj = MySort()
	# Define an array of integers
	arr1 = [3, 6, 2, 5, -7, 2, 1, 4, 7, 8, 2]
	# Get the size of arr
	size = len(arr1)
	print("\n Before Sort :\n", end = "")
	obj.display(arr1, size)
	# Sort element
	obj.tree_sort(arr1, size)
	print("\n After Sort :\n", end = "")
	obj.display(arr1, size)
	arr2 = [8, 2, 9, -6, 3, 2, 31, 41, 2, 1, 67, 32]
	# Get the size of arr
	size = len(arr2)
	print("\n Before Sort :\n", end = "")
	obj.display(arr2, size)
	# Sort element
	obj.tree_sort(arr2, size)
	print("\n After Sort :\n", end = "")
	obj.display(arr2, size)

if __name__ == "__main__": main()

Output

 Before Sort :
  3  6  2  5  -7  2  1  4  7  8  2

 After Sort :
  -7  1  2  2  2  3  4  5  6  7  8

 Before Sort :
  8  2  9  -6  3  2  31  41  2  1  67  32

 After Sort :
  -6  1  2  2  2  3  8  9  31  32  41  67
# 	Ruby Program
# 	Sort array elements by using tree sort

# Binary Search Tree Node
class Node 

	# Define the accessor and reader of class Node  
	attr_reader :data, :left, :right
	attr_accessor :data, :left, :right


	#  Data value 
	
	#  Indicates left and right subtree
	
	def initialize(data)
	
		self.data = data
		self.left = nil
		self.right = nil
	end
end
class MySort 

	# Define the accessor and reader of class MySort  
	attr_reader :root, :location
	attr_accessor :root, :location


	
	def initialize()
	
		self.root = nil
		self.location = 0
	end
	# Function which is display arr elements
	def display(arr, size)
	
		i = 0
		while (i < size)
		
			print(" ", arr[i])
			i += 1
		end
		print("\n")
	end
	# insert a node in BST
	def add(data)
	
		# Create a dynamic node of binary search tree 
		new_node = Node.new(data)
		if (new_node != nil)
		
			if (self.root == nil)
			
				# When adds a first node in tree
				self.root = new_node
			else
			
				find = self.root
				# add new node to proper position
				while (find != nil)
				
					if (find.data >= data)
					
						if (find.left == nil)
						
							find.left = new_node
							return
						else
						
							# visit left sub-tree
							find = find.left
						end
					else
					
						if (find.right == nil)
						
							find.right = new_node
							return
						else
						
							# visit right sub-tree
							find = find.right
						end
					end
				end
			end
		else
		
			print("\nMemory Overflow\n")
		end
	end
	# Add sorted order elements into array
	def inorder_sort(head, arr)
	
		if (head != nil)
		
			head.left = self.inorder_sort(head.left, arr)
			# insert tree elements into array
			arr[@location] = head.data
			self.location = self.location + 1
			head.right = self.inorder_sort(head.right, arr)
			# Safely remove tree element
			if (head.left == nil && head.right == nil)
			
				# When leaf node found then remove current element
				head = nil
			end
		end
		return head
	end
	# Executing the tree sort in given array
	def tree_sort(arr, size)
	
		i = 0
		i = 0
		while (i < size)
		
			self.add(arr[i])
			i += 1
		end
		self.location = 0
		self.root = self.inorder_sort(@root, arr)
	end
end
def main()

	obj = MySort.new()
	# Define an array of integers
	arr1 = [3, 6, 2, 5, -7, 2, 1, 4, 7, 8, 2]
	# Get the size of arr
	size = arr1.length
	print("\n Before Sort :\n")
	obj.display(arr1, size)
	# Sort element
	obj.tree_sort(arr1, size)
	print("\n After Sort :\n")
	obj.display(arr1, size)
	arr2 = [8, 2, 9, -6, 3, 2, 31, 41, 2, 1, 67, 32]
	# Get the size of arr
	size = arr2.length
	print("\n Before Sort :\n")
	obj.display(arr2, size)
	# Sort element
	obj.tree_sort(arr2, size)
	print("\n After Sort :\n")
	obj.display(arr2, size)
end
main()

Output

 Before Sort :
 3 6 2 5 -7 2 1 4 7 8 2

 After Sort :
 -7 1 2 2 2 3 4 5 6 7 8

 Before Sort :
 8 2 9 -6 3 2 31 41 2 1 67 32

 After Sort :
 -6 1 2 2 2 3 8 9 31 32 41 67
/*
	Scala Program
	Sort array elements by using tree sort
*/
//Binary Search Tree Node
class Node(var data: Int,
	var left: Node,
		var right: Node)
{
	def this(data: Int)
	{
		this(data, null, null);
	}
}
class MySort(var root: Node,
	var location: Int)
{
	def this()
	{
		this(null, 0);
	}
	//Function which is display arr elements
	def display(arr: Array[Int], size: Int): Unit = {
		var i: Int = 0;
		while (i < size)
		{
			print(" " + arr(i));
			i += 1;
		}
		print("\n");
	}
	//insert a node in BST
	def add(data: Int): Unit = {
		//Create a dynamic node of binary search tree 
		var new_node: Node = new Node(data);
		if (new_node != null)
		{
			if (this.root == null)
			{
				//When adds a first node in tree
				this.root = new_node;
			}
			else
			{
				var find: Node = this.root;
				//add new node to proper position
				while (find != null)
				{
					if (find.data >= data)
					{
						if (find.left == null)
						{
							find.left = new_node;
							return;
						}
						else
						{
							//visit left sub-tree
							find = find.left;
						}
					}
					else
					{
						if (find.right == null)
						{
							find.right = new_node;
							return;
						}
						else
						{
							//visit right sub-tree
							find = find.right;
						}
					}
				}
			}
		}
		else
		{
			print("\nMemory Overflow\n");
		}
	}
	//Add sorted order elements into array
	def inorder_sort(head: Node, arr: Array[Int]): Node = {
		if (head != null)
		{
          	var temp : Node = head;
			head.left = inorder_sort(head.left, arr);
			//insert tree elements into array
			arr(this.location) = head.data;
			this.location = this.location + 1;
			head.right = inorder_sort(head.right, arr);
			//Safely remove tree element
			if (head.left == null && head.right == null)
			{
				//When leaf node found then remove current element
				temp = null;
              	return temp;
			}
            
		}
		return head;
	}
	//Executing the tree sort in given array
	def tree_sort(arr: Array[Int], size: Int): Unit = {
		var i: Int = 0;
		i = 0;
		while (i < size)
		{
			add(arr(i));
			i += 1;
		}
		this.location = 0;
		this.root = inorder_sort(root, arr);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: MySort = new MySort();
		//Define an array of integers
		var arr1: Array[Int] = Array(3, 6, 2, 5, -7, 2, 1, 4, 7, 8, 2);
		//Get the size of arr
		var size: Int = arr1.length;
		print("\n Before Sort :\n");
		obj.display(arr1, size);
		//Sort element
		obj.tree_sort(arr1, size);
		print("\n After Sort :\n");
		obj.display(arr1, size);
		var arr2: Array[Int] = Array(8, 2, 9, -6, 3, 2, 31, 41, 2, 1, 67, 32);
		//Get the size of arr
		size = arr2.length;
		print("\n Before Sort :\n");
		obj.display(arr2, size);
		//Sort element
		obj.tree_sort(arr2, size);
		print("\n After Sort :\n");
		obj.display(arr2, size);
	}
}

Output

 Before Sort :
 3 6 2 5 -7 2 1 4 7 8 2

 After Sort :
 -7 1 2 2 2 3 4 5 6 7 8

 Before Sort :
 8 2 9 -6 3 2 31 41 2 1 67 32

 After Sort :
 -6 1 2 2 2 3 8 9 31 32 41 67
/*
	Swift Program
	Sort array elements by using tree sort
*/
//Binary Search Tree Node
class Node
{
	// Data value 
	var data: Int;
	// Indicates left and right subtree
	var left: Node? ;
	var right: Node? ;
	init(_ data: Int)
	{
		self.data = data;
		self.left = nil;
		self.right = nil;
	}
}
class MySort
{
	var root: Node? ;
	var location: Int;
	init()
	{
		self.root = nil;
		self.location = 0;
	}
	//Function which is display arr elements
	func display(_ arr: [Int], _ size: Int)
	{
		var i: Int = 0;
		while (i < size)
		{
			print(" ", arr[i], terminator: "");
			i += 1;
		}
		print("\n", terminator: "");
	}
	//insert a node in BST
	func add(_ data: Int)
	{
		//Create a dynamic node of binary search tree 
		let new_node: Node? = Node(data);
		if (new_node != nil)
		{
			if (self.root == nil)
			{
				//When adds a first node in tree
				self.root = new_node;
			}
			else
			{
				var find: Node? = self.root;
				//add new node to proper position
				while (find != nil)
				{
					if (find!.data >= data)
					{
						if (find!.left == nil)
						{
							find!.left = new_node;
							return;
						}
						else
						{
							//visit left sub-tree
							find = find!.left;
						}
					}
					else
					{
						if (find!.right == nil)
						{
							find!.right = new_node;
							return;
						}
						else
						{
							//visit right sub-tree
							find = find!.right;
						}
					}
				}
			}
		}
		else
		{
			print("\nMemory Overflow\n", terminator: "");
		}
	}
	//Add sorted order elements into array
	func inorder_sort(_ head: Node? , _ arr : inout[Int]) -> Node?
	{
		if (head != nil)
		{
			head!.left = self.inorder_sort(head!.left, &arr);
			//insert tree elements into array
			arr[self.location] = head!.data;
			self.location = self.location + 1;
			head!.right = self.inorder_sort(head!.right, &arr);
			//Safely remove tree element
			if (head!.left == nil && head!.right == nil)
			{
				return nil;
			}
		}
		return head;
	}
	//Executing the tree sort in given array
	func tree_sort(_ arr: inout[Int], _ size: Int)
	{
		var i: Int = 0;
		i = 0;
		while (i < size)
		{
			self.add(arr[i]);
			i += 1;
		}
		self.location = 0;
		self.root = self.inorder_sort(self.root, &arr);
	}
}
func main()
{
	let obj: MySort = MySort();
	//Define an array of integers
	var arr1: [Int] = [3, 6, 2, 5, -7, 2, 1, 4, 7, 8, 2];
	//Get the size of arr
	var size: Int = arr1.count;
	print("\n Before Sort :\n", terminator: "");
	obj.display(arr1, size);
	//Sort element
	obj.tree_sort(&arr1, size);
	print("\n After Sort :\n", terminator: "");
	obj.display(arr1, size);
	var arr2: [Int] = [8, 2, 9, -6, 3, 2, 31, 41, 2, 1, 67, 32];
	//Get the size of arr
	size = arr2.count;
	print("\n Before Sort :\n", terminator: "");
	obj.display(arr2, size);
	//Sort element
	obj.tree_sort(&arr2, size);
	print("\n After Sort :\n", terminator: "");
	obj.display(arr2, size);
}
main();

Output

 Before Sort :
  3  6  2  5  -7  2  1  4  7  8  2

 After Sort :
  -7  1  2  2  2  3  4  5  6  7  8

 Before Sort :
  8  2  9  -6  3  2  31  41  2  1  67  32

 After Sort :
  -6  1  2  2  2  3  8  9  31  32  41  67




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