Tree Sort in C++

Data structures and algorithms with C++ is a course that focuses on the fundamentals of computer science. In this course, we will discuss a variety of sorting algorithms and their practical applications. One of the most useful sorting algorithms is tree sort, which is a type of sorting algorithm that uses a binary tree data structure to store and organize data. 

In this article, we will discuss how tree sort works in C++, its time and space complexities, and some examples of how to implement it. We will also discuss some coding exercises you can use to test your understanding of tree sort. 

What is Tree Sort?

Tree sort is an in-place sorting algorithm that uses a binary tree data structure to store and organize data. It is also known as a binary tree sort or an ordered binary tree sort. The basic idea behind tree sort is to create a binary tree from the data set, then traverse the tree in order to sort the data.

Tree sort is considered to be a fast and efficient sorting algorithm, as it can be completed in O(n log n) time, and it does not require any extra space. However, it can be difficult to implement, as it requires a good understanding of binary trees and their operations.

How Tree Sort Works in C++

Tree sort works by first creating a binary tree from the data set. To do this, we start with an empty binary tree and add each element of the data set one at a time. We add each element by comparing it to the root node of the tree and then inserting it in the left subtree if it is less than the root, or in the right subtree if it is greater than the root. 

Once the binary tree is created, we can use an in-order traversal to traverse the tree and sort the data. An in-order traversal visits the left subtree, then the root node, then the right subtree. This ensures that the elements in the tree are visited in sorted order, from smallest to largest.  

Once the tree is traversed, the elements will be sorted in ascending order. We can then store the sorted elements in an array and return it as the result of the tree sort algorithm.

Below is an example of how to implement tree sort in C++:

// C++ implementation of Tree Sort 
#include<iostream> 
using namespace std; 

// A binary tree node has data, pointer to left child 
// and a pointer to right child 
struct Node 
{ 
	int data; 
	Node* left; 
	Node* right; 
}; 

// Function to create a new node 
Node* newNode(int data) 
{ 
	Node* node = new Node; 
	node->data = data; 
	node->left = NULL; 
	node->right = NULL; 

	return node; 
} 

// Function to traverse the binary tree in-order 
// and store the result in an array 
void inOrder(Node* root, int arr[], int& index) 
{ 
	// Base case 
	if (root == NULL) 
		return; 

	// Traverse the left subtree 
	inOrder(root->left, arr, index); 

	// Add the data of the node to the array 
	arr[index] = root->data; 
	index++; 

	// Traverse the right subtree 
	inOrder(root->right, arr, index); 
} 

// Function to perform tree sort 
void treeSort(int arr[], int n) 
{ 
	Node* root = NULL; 

	// Create a binary tree from the given array 
	for (int i = 0; i < n; i++) 
		root = Insert(root, arr[i]); 

	// Traverse the binary tree in-order and store 
	// the result in an array 
	int index = 0; 
	inOrder(root, arr, index); 
} 

// Function to insert a node in the binary tree 
Node* Insert(Node* root, int data) 
{ 
	if (root == NULL) 
		return newNode(data); 

	if (data < root->data) 
		root->left = Insert(root->left, data); 
	else
		root->right = Insert(root->right, data); 

	return root; 
} 

// Driver program 
int main() 
{ 
	int arr[] = {4, 2, 5, 1, 3}; 
	int n = sizeof(arr)/sizeof(arr[0]); 

	cout << "Given array is \n"; 
	for (int i = 0; i < n; i++) 
		cout << arr[i] << " "; 

	treeSort(arr, n); 

	cout << "\nSorted array is \n"; 
	for (int i = 0; i < n; i++) 
		cout << arr[i] << " "; 
	return 0; 
} 

Time Complexity of Tree Sort

The time complexity of tree sort is O(n log n), which is the same as the time complexity of other sorting algorithms such as quicksort and heapsort. This is because tree sort requires the same amount of time to create the binary tree and to traverse it. 

The best-case time complexity of tree sort is O(n log n), which occurs when the binary tree is perfectly balanced. The worst-case time complexity is also O(n log n), which occurs when the binary tree is not perfectly balanced. 

Space Complexity of Tree Sort

The space complexity of tree sort is O(n), which is the same as the space complexity of other sorting algorithms such as quicksort and heapsort. This is because tree sort does not require any extra space for sorting. 

Conclusion

In this article, we discussed tree sort, an in-place sorting algorithm that uses a binary tree data structure to store and organize data. We discussed how tree sort works in C++ and its time and space complexities. We also looked at an example of how to implement tree sort in C++. 

Tree sort is a fast and efficient sorting algorithm, as it can be completed in O(n log n) time and does not require any extra space. However, it can be difficult to implement, as it requires a good understanding of binary trees and their operations.

Exercises

// Function to insert a node into a binary tree 
Node* Insert(Node* root, int data) 
{ 
	if (root == NULL) 
		return newNode(data); 

	if (data < root->data) 
		root->left = Insert(root->left, data); 
	else
		root->right = Insert(root->right, data); 

	return root; 
} 

// Function to traverse the binary tree in-order and store 
// the result in an array 
void inOrder(Node* root, int arr[], int& index) 
{ 
	// Base case 
	if (root == NULL) 
		return; 

	// Traverse the left subtree 
	inOrder(root->left, arr, index); 

	// Add the data of the node to the array 
	arr[index] = root->data; 
	index++; 

	// Traverse the right subtree 
	inOrder(root->right, arr, index); 
}