Tree Sort Implementation in Python

Tree Sort is a sorting algorithm that works by creating a binary search tree from an input array of elements, and then traversing the tree in-order to retrieve the elements in sorted order. In this article, we will discuss how Tree Sort works, its implementation in Python, and its time and space complexity.

How Algorithm Works

The algorithm works by first inserting each element from the input array into a binary search tree. A binary search tree is a data structure that consists of a root node, and two subtrees – one containing elements smaller than the root, and one containing elements larger than the root. When inserting an element into the tree, we traverse the tree from the root downwards, comparing the element to each node we encounter along the way, and inserting it as a leaf node when we reach an empty subtree.

Once all elements have been inserted into the tree, we traverse the tree in-order, retrieving the elements in sorted order. In-order traversal of a binary search tree involves first visiting the left subtree, then the root, and then the right subtree.

Algorithm Implementation

Here is the implementation of Tree Sort in Python:

class TreeNode:
    def __init__(self, val=None):
        self.val = val
        self.left = None
        self.right = None

def insert_node(root, val):
    if root is None:
        return TreeNode(val)
    if val < root.val:
        root.left = insert_node(root.left, val)
    else:
        root.right = insert_node(root.right, val)
    return root

def in_order_traversal(root):
    if root:
        in_order_traversal(root.left)
        print(root.val, end=' ')
        in_order_traversal(root.right)

def tree_sort(arr):
    root = None
    for val in arr:
        root = insert_node(root, val)
    in_order_traversal(root)

The above implementation creates a binary search tree from the input array using the insert_node() function, and then traverses the tree in-order to retrieve the elements in sorted order using the in_order_traversal() function. Finally, the sorted elements are printed to the console using the print() function.

The insert_node() function takes a root node and a value as input, and returns the modified root node with the value inserted into the tree. If the root node is None, it creates a new TreeNode object with the given value. If the value is less than the value of the current node, it recursively inserts the value into the left subtree. Otherwise, it recursively inserts the value into the right subtree.

The in_order_traversal() function takes a root node as input, and recursively traverses the tree in-order, printing each node value to the console as it is visited.

The tree_sort() function takes an array as input, creates a binary search tree from the array using the insert_node() function, and then traverses the tree in-order using the in_order_traversal() function to retrieve the elements in sorted order.

Time and Space Complexity

The time complexity of Tree Sort is O(n log n) for average and worst case, as each element must be inserted into the binary search tree, and then the tree must be traversed in-order to retrieve the sorted elements. The space complexity of Tree Sort is O(n), as we create a binary search tree containing n elements.

Example

Let’s see an example of Tree Sort in action:

arr = [3, 7, 4, 8, 6, 2, 1, 5]
tree_sort(arr)

The above code will output:

1 2 3 4 5 6 7 8 

Here, we create an input array arr containing 8 integers. We then call the tree_sort() function with arr as input, which sorts the elements and prints them in sorted order.

Conclusion

Tree Sort is a simple and efficient sorting algorithm that works by creating a binary search tree from an input array, and then traversing the tree in-order to retrieve the elements in sorted order. Its time complexity of O(n log n) and space complexity of O(n) make it a good choice for sorting small to medium-sized arrays. The Python implementation we discussed here is easy to understand and implement, and can be useful for sorting applications where preserving the original order of equal elements is not important.