tree sort Algorithm

Tree Sort Algorithm is a sorting technique that follows a binary search tree data structure, a tree-based algorithm used for sorting elements in a specific order. It is a comparison-based sorting method, where the elements are organized in a hierarchical structure called the binary search tree. In this structure, each node has at most two children, and the left child node has a value less than or equal to its parent, while the right child node has a value greater than or equal to its parent. The basic idea behind the Tree Sort Algorithm is to insert elements from the input array into a binary search tree, and then traverse the tree in an inorder manner to obtain the sorted elements. To implement the Tree Sort Algorithm, first, the elements are inserted one by one into a binary search tree. This is done by comparing the incoming element with the value of the current node, and if it is less than or equal to the current node's value, it is inserted into the left subtree, otherwise, it is inserted into the right subtree. This process is repeated until all the elements from the input array have been inserted into the tree. After the insertion is completed, an inorder traversal of the binary search tree is performed, which gives the sorted elements in an ascending order. During the inorder traversal, the algorithm visits the left subtree, the current node, and then the right subtree recursively, thus producing a sorted sequence of elements. The time complexity of the Tree Sort Algorithm is O(n log n) for balanced trees, but it can be as bad as O(n^2) for skewed trees, making it less efficient for certain cases.
"""
Tree_sort algorithm.

Build a BST and in order traverse.
"""


class node:
    # BST data structure
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

    def insert(self, val):
        if self.val:
            if val < self.val:
                if self.left is None:
                    self.left = node(val)
                else:
                    self.left.insert(val)
            elif val > self.val:
                if self.right is None:
                    self.right = node(val)
                else:
                    self.right.insert(val)
        else:
            self.val = val


def inorder(root, res):
    # Recursive traversal
    if root:
        inorder(root.left, res)
        res.append(root.val)
        inorder(root.right, res)


def tree_sort(arr):
    # Build BST
    if len(arr) == 0:
        return arr
    root = node(arr[0])
    for i in range(1, len(arr)):
        root.insert(arr[i])
    # Traverse BST in order.
    res = []
    inorder(root, res)
    return res


if __name__ == "__main__":
    print(tree_sort([10, 1, 3, 2, 9, 14, 13]))

LANGUAGE:

DARK MODE: