Tree Sort - Example

Example

The following tree sort algorithm in pseudocode accepts an array of comparable items and prints them to the screen in ascending order:

STRUCTURE BinaryTree BinaryTree:LeftSubTree Object:Node BinaryTree:RightSubTree END STRUCTURE PROCEDURE Insert(BinaryTree:searchTree, Object:item) IF searchTree IS NULL THEN SET searchTree.Node TO item ELSE IF item IS LESS THAN searchTree.Node THEN Insert(searchTree.LeftSubTree, item) ELSE Insert(searchTree.RightSubTree, item) END IF END IF END PROCEDURE PROCEDURE InOrder(BinaryTree:searchTree) IF searchTree IS NULL THEN EXIT PROCEDURE ELSE InOrder(searchTree.LeftSubTree) PRINT searchTree.Node InOrder(searchTree.RightSubTree) END IF END PROCEDURE PROCEDURE TreeSort(Array:items) BinaryTree:searchTree FOR EACH individualItem IN items Insert(searchTree, individualItem) END FOR InOrder(searchTree) END PROCEDURE

In a simple functional programming form, the algorithm (in Haskell) would look something like this:

data Tree a = Leaf | Node (Tree a) a (Tree a) insert :: Ord a => a -> Tree a -> Tree a insert x Leaf = Node Leaf x Leaf insert x (Node t y s) | x <= y = Node (insert x t) y s insert x (Node t y s) | x > y = Node t y (insert x s) flatten :: Tree a -> flatten Leaf = flatten (Node t x s) = flatten t ++ ++ flatten s treesort :: Ord a => -> treesort = flatten . foldr insert Leaf

Mind that in the above example, both the insertion algorithm and the retrieval algorithm have O(n2) worst case scenarios.