Python: Sort a list of elements using Tree sort

Last update on April 02 2025 05:26:01 (UTC/GMT +8 hours)

23. Tree Sort

Write a Python program to sort a list of elements using Tree sort.

Sample Solution:

Python Code:

# License https://bit.ly/2InTS3W
# 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 travesal 
    if root:
        inorder(root.left,res)
        res.append(root.val)
        inorder(root.right,res)

def treesort(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

print(treesort([7,1,5,2,19,14,17]))

Sample Output:

[1, 2, 5, 7, 14, 17, 19]

Flowchart:

For more Practice: Solve these Related Problems:

• Write a Python program to implement tree sort by inserting elements into a binary search tree and then performing an in-order traversal.
• Write a Python script to sort a list of numbers using tree sort and then print the tree structure along with the sorted list.
• Write a Python program to use tree sort on a list of strings and then verify that the sort is stable.
• Write a Python function to implement tree sort and then compare its performance with quick sort on a random list.

Python Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a Python program to sort a list of elements using Topological sort.
Next: Write a Python program to sort an unsorted array numbers using Wiggle sort.