What is tree sort?

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.

Algorithm steps

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:

# The Node class with a default constructor
class Node:
    def __init__(self, key):
        self.key = key      # parameter to hold the value
        self.left = None    # parameter to hold the left sub-tree
        self.right = None   # parameter to hold the right sub-tree
# Implementation of binarySearchTree class    
class binarySearchTree:
    def __init__(self):
        self.root = None    # parameter to hold the root node
    
    # The insert() function to add a new Node to the BST
    def insert(self, key):
        self.root = self.insertNode(self.root, key)
        
    # A helper function to add a new node recursively
    def insertNode(self, root, key):
        # If the root is None (empty Node), return a new node
        if root is None:
            return Node(key)
        # If the key is smaller that root value, call insertNode() to add Node in left subtree
        if key < root.key:
            root.left = self.insertNode(root.left, key)      
        # otherwise, call insertNode() to add Node in right subtree
        else: 
            root.right = self.insertNode(root.right, key)
        return root
      
    # The inOrderTraversal function to do in-order tree traversal 
    def inOrderTraversal(self):
        output = []
        self.traverseBST(self.root, output)
        return output
    # A helper function to traverse tree recursively
    def 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 sorting
def treeSort(arr): 
    bst = binarySearchTree()
    # Adding elements to the binary search tree
    for element in arr:
        bst.insert(element)
    # returning the in-order traversal of the binary search tree
    return bst.inOrderTraversal()
arr = [14, 13, 18, 11, 19, 12, 15, 16]
print("Unsorted array:", arr)
arr = treeSort(arr)
print("Sorted array:", arr)

Code explanation

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.

Complexity

The time complexity of the tree sort depends on the shape of the binary search tree. If the tree is skewedA skewed Binary Search Tree (BST) is one where all nodes have only one or no child, causing the tree to lean entirely to the left or right. to one side (like a linked list), the time complexity would be $O(n^2)$ . However, the average time complexity of the tree sort is $O(n\;log(n))$ , which makes it comparable with other efficient sorting algorithms like merge sort, quick sort, timsort, etc.

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 $O(n)$ .

Benefits and limitations

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

Benefits

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.

Limitations

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.

Optimization

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.

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments