Tree sort is a sorting algorithm that builds a Binary Search Tree (BST) from the elements of the array to be sorted and then performs an in-order traversal of the BST to get the elements in sorted order. In this article, we will learn about the basics of Tree Sort along with its implementation in Python.

What is Tree Sort?

Tree sort is a comparison-based sorting algorithm that uses a Binary Search Tree (BST) to sort elements. The algorithm inserts all elements into the BST, and then an in-order traversal of the tree retrieves the elements in sorted order.

Working of Tree Sort:

Tree sort uses the properties of BST, where each node has at most two children, referred to as the left and right child. For any given node:

• The left child’s value is less than the node’s value.
• The right child’s value is greater than the node’s value.

Tree Sort involves two main steps:

1. Insertion: Insert all elements into the BST.
2. Traversal: Perform an in-order traversal of the BST to extract the elements in sorted order.

Tree Sort in Python:

Step 1: Define the Node Class:

First, we define a class for the nodes of the binary search tree.

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

Step 2: Inserting Elements into the BST:

Next, we define a function to insert elements into the binary search tree.

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

Step 3: In-Order Traversal of the BST:

The in-order traversal function will visit all nodes of the BST in sorted order and collect the elements.

def inorder_traversal(root, res):
    if root:
        inorder_traversal(root.left, res)
        res.append(root.val)
        inorder_traversal(root.right, res)

Step 4: Tree Sort Function:

Now, we combine the insertion and in-order traversal steps to implement the tree sort function.

def tree_sort(arr):
    if not arr:
        return arr
    
    root = None
    for key in arr:
        root = insert(root, key)
    
    sorted_arr = []
    inorder_traversal(root, sorted_arr)
    return sorted_arr

Complete implementation of Tree Sort in Python:

Here is the complete implementation of tree sort in Python:

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

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

def inorder_traversal(root, res):
    if root:
        inorder_traversal(root.left, res)
        res.append(root.val)
        inorder_traversal(root.right, res)

def tree_sort(arr):
    if not arr:
        return arr
    
    root = None
    for key in arr:
        root = insert(root, key)
    
    sorted_arr = []
    inorder_traversal(root, sorted_arr)
    return sorted_arr

# Example usage
arr = [5, 3, 7, 2, 8, 1, 4, 6]
sorted_arr = tree_sort(arr)
print("Sorted array:", sorted_arr)

Sorted array: [1, 2, 3, 4, 5, 6, 7, 8]

Time Complexity: O(nlogn) on average, but it can degrade to O(n^2) if the tree becomes unbalanced (e.g., if the input array is already sorted).

Auxiliary Space: O(n)