Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
Tree sort is an online sorting algorithm that builds a binary search tree from the elements to be sorted, and then traverses the tree (in-order) so that the elements come out in sorted order.
Steps:
- Step 1: Take the elements input in an array.
- Step 2: Create a Binary search tree by inserting data items from the array into the binary searh tree.
- Step 3: Perform in-order traversal on the tree to get the elements in sorted order.
Complexity
- Worst case time complexity:
Θ(N log N)using balanced binary search tree;Θ(N^2)using unbalanced binary search tree. - Average case time complexity:
Θ(N log N) - Best case time complexity:
Θ(N log N) - Space complexity:
Θ(N).
Implementations
Implementation of Tree Sort algorithm in 6 languages that includes C, C++, Java, Go, JavaScript and Python.
- C
- C++
- Java
- Go
- JavaScript
- Python
C
#include <stdio.h>
#include <alloc.h>
// Part of Cosmos by OpenGenus Foundation
struct btreenode
{
struct btreenode *leftchild ;
int data ;
struct btreenode *rightchild ;
} ;
void insert ( struct btreenode **, int ) ;
void inorder ( struct btreenode * ) ;
void main( )
{
struct btreenode *bt ;
int arr[10] = { 11, 2, 9, 13, 57, 25, 17, 1, 90, 3 } ;
int i ;
bt = NULL ;
printf ( "Binary tree sort.\n" ) ;
printf ( "\nArray:\n" ) ;
for ( i = 0 ; i <= 9 ; i++ )
printf ( "%d\t", arr[i] ) ;
for ( i = 0 ; i <= 9 ; i++ )
insert ( &bt, arr[i] ) ;
printf ( "\nIn-order traversal of binary tree:\n" ) ;
inorder ( bt ) ;
}
void insert ( struct btreenode **sr, int num )
{
if ( *sr == NULL )
{
*sr = malloc ( sizeof ( struct btreenode ) ) ;
( *sr ) -> leftchild = NULL ;
( *sr ) -> data = num ;
( *sr ) -> rightchild = NULL ;
}
else
{
if ( num < ( *sr ) -> data )
insert ( &( ( *sr ) -> leftchild ), num ) ;
else
insert ( &( ( *sr ) -> rightchild ), num ) ;
}
}
void inorder ( struct btreenode *sr )
{
if ( sr != NULL )
{
inorder ( sr -> leftchild ) ;
printf ( "%d\t", sr -> data ) ;
inorder ( sr -> rightchild ) ;
}
}
C++
//Tree Sort implemented using C++
// Part of Cosmos by OpenGenus Foundation
#include <vector>
#include <iostream>
using namespace std;
struct Node
{
int data;
struct Node *left,*right;
};
//Function to create new Node
struct Node *newnode(int key)
{
struct Node *temp=new Node;
temp->data=key;
temp->left=NULL;
temp->right=NULL;
return temp;
}
Node* insert(Node *node,int key)
{
if(node==NULL) return newnode(key);//If tree is empty return new node
if(key < node->data)
node->left=insert(node->left,key);
else
node->right=insert(node->right,key);
return node;
}
void store(Node *root,int a[],int &i)
{
if(root!=NULL)
{
store(root->left,a,i);
a[i++]=root->data;
store(root->right,a,i);
}
}
void TreeSort(vector<int>& a)
{
struct Node *root = NULL;
//Construct binary search tree
root = insert(root, a[0]);
for (size_t i=1; i<a.size(); i++)
insert(root, a[i]);
//Sorting the array using inorder traversal on BST
int i = 0;
store(root, a.data() , i);
}
int main()
{
vector<int> a{1,6,8,3,10,2,12};
TreeSort(a);
cout<<"The sorted array is :\n";
//Printing the sorted array
for(size_t i=0;i<a.size();i++)
{
cout<<a[i]<<" ";
}
return 0;
}
/* output:
The sorted array is :
1 2 3 6 8 10 12
*/
Java
// Part of Cosmos by OpenGenus Foundation
public class Tree {
public static void main(String[] args) {
TreeSort myTree;
myTree = new TreeSort(4);
myTree.invert(new TreeSort(5));
myTree.invert(new TreeSort(8));
myTree.invert(new TreeSort(1));
myTree.traverse(new KeyPrint());
}
static class TreeSort {
private TreeSort left;
private TreeSort right;
private int key;
public TreeSort(int key) {
this.key = key;
}
private void invert(TreeSort node) {
if (node.key < key) {
if (left != null) left.invert(node);
else {
left = node;
}
} else {
if (right != null) right.invert(node);
else {
right = node;
}
}
}
private void traverse(TreeVisitor visitor) {
if (left != null)
left.traverse(visitor);
visitor.visit(this);
if (right != null)
right.traverse(visitor);
}
}
interface TreeVisitor {
void visit(TreeSort node);
}
static class KeyPrint implements TreeVisitor {
public void visit(TreeSort node) {
System.out.println(" " + node.key);
}
}
}
Go
package main
import "fmt"
// Part of Cosmos by OpenGenus Foundation
/**************************************
* Structures
**************************************/
// Define binary tree structure
//
// - data : the value in the tree
// - right : the sub-tree of greater or equal values
// - left : the sub-tree of lesser values
type Tree struct {
data int
right *Tree
left *Tree
}
// Create a Tree by initializing its subtree to nil
// and setting it's value.
func createTree(value int) *Tree {
var tree = Tree{}
tree.data = value
tree.right = nil
tree.left = nil
return &tree
}
// Insert the given value in the tree.
//
// The tree is traveled until an empty sub-tree is found:
// If the value is lesser than the one hold by the current node,
// try to insert it to the left.
// If the value is greater or equal than the one hold by the current node,
// try to insert it to the right.
// The value is inserted by creating a new sub-tree.
func (t *Tree) insert(value int) *Tree {
if value < t.data {
if t.left == nil {
t.left = createTree(value)
} else {
t.left.insert(value)
}
} else {
if t.right == nil {
t.right = createTree(value)
} else {
t.right.insert(value)
}
}
return t
}
// Apply the given function to each value in the tree
// from left to right, i.e. from the lesser one to the greater one.
func (t *Tree) forEach(fn func(int)) {
if t.left != nil {
t.left.forEach(fn)
}
fn(t.data)
if t.right != nil {
t.right.forEach(fn)
}
}
/**************************************
* Algorithm
**************************************/
// Perform a binary tree sort of the given array
// and return the created tree.
func binaryTreeSort(array []int) *Tree {
tree := createTree(array[0])
for _, node := range array[1:] {
tree.insert(node)
}
return tree
}
/**************************************
* Tests
**************************************/
// Test the binary tree sort on the given array:
//
// [1, -6, 8, 3, 10, 3, 21]
//
// Should output: -6 1 3 3 8 10 21
//
// NOTE: this will only display the values in the tree by traveling
// it from left to right.
// If you want to fill an array with the values,
// just pass a function that fills it to tree.forEach().
func main() {
var array = [...]int{1,-6,8,3,10,3,21}
tree := binaryTreeSort(array[:])
tree.forEach(func(value int) {
fmt.Print(value, " ")
})
}
JavaScript
// Part of Cosmos by OpenGenus Foundation
var BinarySearchTree = function(value) {
var instance = Object.create(BinarySearchTree.prototype);
instance.value = value;
// a BST where all values are higher than than the current value.
instance.right = undefined;
// a binary search tree (BST) where all values are lower than than the current value.
instance.left = undefined;
return instance
};
BinarySearchTree.prototype.insert = function (value) {
// accepts a value and places in the tree in the correct position.
var node = BinarySearchTree(value);
function recurse(bst) {
if (bst.value > value && bst.left === undefined) {
bst.left = node;
} else if (bst.value > value) {
recurse(bst.left);
} else if (bst.value < value && bst.right === undefined) {
bst.right = node;
} else if (bst.value < value) {
recurse(bst.right);
}
}
recurse(this);
}
BinarySearchTree.prototype.contains = function (value) {
var doesContain = false;
//accepts a value and returns a boolean reflecting whether or not the value is contained in the tree.
function recurse(bst) {
if (bst.value === value) {
doesContain = true;;
} else if (bst.left !== undefined && value < bst.value) {
recurse(bst.left);
} else if (bst.right !== undefined && value > bst.value) {
recurse(bst.right)
}
}
recurse(this);
return doesContain;
}
BinarySearchTree.prototype.depthFirstLog = function (callback) {
//accepts a callback and executes it on every value contained in the tree.
function recurse(bst) {
callback.call(bst, bst.value)
if (bst.left !== undefined) {
recurse(bst.left)
}
if (bst.right !== undefined) {
recurse(bst.right);
}
}
recurse(this);
}
Python
# Part of Cosmos by OpenGenus Foundation
class Node:
"""Base class to contain the tree metadata per instance of the class"""
def __init__(self, val):
self.l_child = None
self.r_child = None
self.data = val
def binary_insert(root, node):
"""This recursive function will insert the objects into the tree"""
if root is None: # If we don't have a root node
root = node # Set the root node equal to the first node argument that was provided
else: # We already have a root
if root.data > node.data: # If our current root is bigger than the node we are about to insert
if root.l_child is None: # If we don't have any node to the left of root
root.l_child = node # Insert the node as the left node under root
else: # There's already a node to the left of root
binary_insert(
root.l_child, node
) # Call the insert function recursively with the left node value as the
# temp root for comparison
else: # Node to be inserted is bigger than root (going right side)
if root.r_child is None: # if there's no right child
root.r_child = node # insert the node as the right child of root (under)
else: #
binary_insert(
root.r_child, node
) # Call the insert function recursively with the right node value as the
# temp root for comparison
def post_sort_print(root):
if not root:
return None
post_sort_print(root.l_child)
print(root.data)
post_sort_print(root.r_child)
def pre_sort_print(root):
if not root:
return None
print(root.data)
pre_sort_print(root.l_child)
pre_sort_print(root.r_child)
r = Node(6)
binary_insert(r, Node(2))
binary_insert(r, Node(8))
binary_insert(r, Node(90))
binary_insert(r, Node(23))
binary_insert(r, Node(12))
binary_insert(r, Node(91))
print("---------")
print("PRE SORT")
pre_sort_print(r)
print("---------")
print("POST SORT")
post_sort_print(r)
Applications
-
Its typical use is sorting elements online: after each insertion, the set of elements seen so far is available in sorted order.
-
When using a splay tree as the binary search tree, the resulting algorithm (called splaysort) has the additional property that it is an adaptive sort, meaning that its running time is faster than O(n log n) for inputs that are nearly sorted.
