The **tree sort** is a unique sorting algorithm that uses the binary search tree for sorting purposes. The algorithm of the tree sort builds a binary search tree from the given array and performs an in-order traversal of the tree to obtain the elements in sorted order. It falls under the comparison-based sorting algorithms, where the arrangement of elements is determined by comparing them pairwise in the building process of the binary search tree.

Let’s pen down the steps of the tree sort:

Build a binary search tree.

Perform the in-order traversal.

Play the following slides to visualize the working of the tree sort:

Let’s implement the Python code of the tree sort in the following playground:

# The Node class with a default constructorclass Node:def __init__(self, key):self.key = key # parameter to hold the valueself.left = None # parameter to hold the left sub-treeself.right = None # parameter to hold the right sub-tree# Implementation of binarySearchTree classclass binarySearchTree:def __init__(self):self.root = None # parameter to hold the root node# The insert() function to add a new Node to the BSTdef insert(self, key):self.root = self.insertNode(self.root, key)# A helper function to add a new node recursivelydef insertNode(self, root, key):# If the root is None (empty Node), return a new nodeif root is None:return Node(key)# If the key is smaller that root value, call insertNode() to add Node in left subtreeif key < root.key:root.left = self.insertNode(root.left, key)# otherwise, call insertNode() to add Node in right subtreeelse:root.right = self.insertNode(root.right, key)return root# The inOrderTraversal function to do in-order tree traversaldef inOrderTraversal(self):output = []self.traverseBST(self.root, output)return output# A helper function to traverse tree recursivelydef traverseBST(self, root, output):if root:self.traverseBST(root.left, output)output.append(root.key)self.traverseBST(root.right, output)return# The treeSort function to perform sortingdef treeSort(arr):bst = binarySearchTree()# Adding elements to the binary search treefor element in arr:bst.insert(element)# returning the in-order traversal of the binary search treereturn bst.inOrderTraversal()arr = [14, 13, 18, 11, 19, 12, 15, 16]print("Unsorted array:", arr)arr = treeSort(arr)print("Sorted array:", arr)

Let’s discuss the code below:

**Lines 2–6:**We define the`Node`

class with a default constructor. It has three parameters: The`key`

to store the data,`left`

and`right`

to store the reference to the left and right sub-trees.**Lines 9–42:**We define the`binarySearchTree`

class to implement the binary search tree. Inside this class:**Lines 10–11:**We define a default constructor to initialize the`root`

of the tree.**Lines 14–28:**We define two functions to perform the insert operation of the binary search tree. The`insert()`

function calls the`insertNode()`

function with the`root`

parameter to add the`key`

to the binary search tree. The`insertNode()`

function returns the object of the`Node`

class with`key`

if the current node`root`

is`None`

. Otherwise, the target node is found to add the`key`

node recursively. Lastly, the`insertNode()`

function returns the root of the binary tree.**Lines 31–42:**We define two functions to perform in-order traversal of the binary search tree. The`inOrderTraversal()`

function creates a list`output`

, calls the`traverseBST()`

function to store the in-order traversal into the`output`

list, and returns the`output`

. The`traverseBST()`

function traverses the tree to the`left`

leaf node recursively, append the node value to the`output`

list, and traverses the right sub-tree recursively.

**Lines 45–51:**We define the`treeSort()`

function to implement the tree sort algorithm. This function receives the array`arr`

to sort as a parameter. Inside this function:**Line 46:**We define an object`bst`

of the`binarySearchTree`

class.**Lines 48**–**49:**We traverse the`arr`

list using the`for`

loop and insert the array into the binary search tree.**Line 51:**We return the in-order traversal by calling the`inOrderTraversal()`

function of the binary search tree class.

**Lines 53–54:**We create an unsorted array and print the array before sorting.**Lines 56–57:**We call the`treeSort()`

function and print the array after sorting.

The time complexity of the tree sort depends on the shape of the binary search tree. If the tree is

**Best-case time complexity:**$O(n\;log(n))$ **Average-case time complexity:**$O(n\;log(n))$ **Worst-case time complexity:**$O(n^2)$

Since the tree sort builds a binary search tree of the given array, the space complexity is

Let’s discuss some benefits and limitations of the tree sort.

The tree sort is a stable sorting algorithm, which means it takes care of the relative positions of similar elements.

It is an online sorting algorithm, which means it doesn’t require the complete data to start the sorting.

It is efficient for small to medium size datasets.

The worst-case time complexity is

$O(n^2)$ , which is a limiting factor to applying this algorithm on a large dataset.It requires extra memory space to build a binary search tree.

In the case of sorted elements, the binary search tree will be skewed to one side, similar to a linked list. In that scenario, the tree sort can be optimized by using an AVL tree to avoid the skewed version of the binary search tree. The AVL tree is a balanced binary tree that automatically re-arranges its elements to maintain the lowest depth of the binary search tree.

Let’s test your understanding by connecting to the correct answer.

Match The Answer

Select an option from the left-hand side

Best-case time complexity

$O(1)$

Average-case time complexity

$O(n)$

Worst-case time complexity

$O(n\;log(n))$

Space complexity

$O(n^2)$

Copyright ©2024 Educative, Inc. All rights reserved

TRENDING TOPICS