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.
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
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.
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.
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.
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.
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.