Tree Sort
Tree sort is a sorting algorithm that is based on Binary Search Tree data structure. It first creates a binary search tree from the elements of the input list or array and then performs an in-order traversal on the created binary search tree to get the elements in sorted order.
Algorithm:
- 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 search tree.
- Step 3: Perform in-order traversal on the tree to get the elements in sorted order.
Applications of Tree sort:
- Its most common use is to edit the elements online: after each installation, a set of objects seen so far is available in a structured program.
- If you use a splay tree as a binary search tree, the resulting algorithm (called splaysort) has an additional property that it is an adaptive sort, which means its working time is faster than O (n log n) for virtual inputs.
Below is the implementation for the above approach:
C++
// C++ program to implement Tree Sort #include<bits/stdc++.h> using namespace std; struct Node { int key; struct Node *left, *right; }; // A utility function to create a new BST Node struct Node *newNode( int item) { struct Node *temp = new Node; temp->key = item; temp->left = temp->right = NULL; return temp; } // Stores inorder traversal of the BST // in arr[] void storeSorted(Node *root, int arr[], int &i) { if (root != NULL) { storeSorted(root->left, arr, i); arr[i++] = root->key; storeSorted(root->right, arr, i); } } /* A utility function to insert a new Node with given key in BST */ Node* insert(Node* node, int key) { /* If the tree is empty, return a new Node */ if (node == NULL) return newNode(key); /* Otherwise, recur down the tree */ if (key < node->key) node->left = insert(node->left, key); else if (key > node->key) node->right = insert(node->right, key); /* return the (unchanged) Node pointer */ return node; } // This function sorts arr[0..n-1] using Tree Sort void treeSort( int arr[], int n) { struct Node *root = NULL; // Construct the BST root = insert(root, arr[0]); for ( int i=1; i<n; i++) root = insert(root, arr[i]); // Store inorder traversal of the BST // in arr[] int i = 0; storeSorted(root, arr, i); } // Driver Program to test above functions int main() { //create input array int arr[] = {5, 4, 7, 2, 11}; int n = sizeof (arr)/ sizeof (arr[0]); treeSort(arr, n); for ( int i=0; i<n; i++) cout << arr[i] << " " ; return 0; } |
Java
// Java program to // implement Tree Sort class GFG { // Class containing left and // right child of current // node and key value class Node { int key; Node left, right; public Node( int item) { key = item; left = right = null ; } } // Root of BST Node root; // Constructor GFG() { root = null ; } // This method mainly // calls insertRec() void insert( int key) { root = insertRec(root, key); } /* A recursive function to insert a new key in BST */ Node insertRec(Node root, int key) { /* If the tree is empty, return a new node */ if (root == null ) { root = new Node(key); return root; } /* Otherwise, recur down the tree */ if (key < root.key) root.left = insertRec(root.left, key); else if (key > root.key) root.right = insertRec(root.right, key); /* return the root */ return root; } // A function to do // inorder traversal of BST void inorderRec(Node root) { if (root != null ) { inorderRec(root.left); System.out.print(root.key + " " ); inorderRec(root.right); } } void treeins( int arr[]) { for ( int i = 0 ; i < arr.length; i++) { insert(arr[i]); } } // Driver Code public static void main(String[] args) { GFG tree = new GFG(); int arr[] = { 5 , 4 , 7 , 2 , 11 }; tree.treeins(arr); tree.inorderRec(tree.root); } } // This code is contributed // by Vibin M |
Python3
# Python3 program to # implement Tree Sort # Class containing left and # right child of current # node and key value class Node: def __init__( self ,item = 0 ): self .key = item self .left, self .right = None , None # Root of BST root = Node() root = None # This method mainly # calls insertRec() def insert(key): global root root = insertRec(root, key) # A recursive function to # insert a new key in BST def insertRec(root, key): # If the tree is empty, # return a new node if (root = = None ): root = Node(key) return root # Otherwise, recur # down the tree if (key < root.key): root.left = insertRec(root.left, key) elif (key > root.key): root.right = insertRec(root.right, key) # return the root return root # A function to do # inorder traversal of BST def inorderRec(root): if (root ! = None ): inorderRec(root.left) print (root.key ,end = " " ) inorderRec(root.right) def treeins(arr): for i in range ( len (arr)): insert(arr[i]) # Driver Code arr = [ 5 , 4 , 7 , 2 , 11 ] treeins(arr) inorderRec(root) # This code is contributed by shinjanpatra |
C#
// C# program to // implement Tree Sort using System; public class GFG { // Class containing left and // right child of current // node and key value public class Node { public int key; public Node left, right; public Node( int item) { key = item; left = right = null ; } } // Root of BST Node root; // Constructor GFG() { root = null ; } // This method mainly // calls insertRec() void insert( int key) { root = insertRec(root, key); } /* A recursive function to insert a new key in BST */ Node insertRec(Node root, int key) { /* If the tree is empty, return a new node */ if (root == null ) { root = new Node(key); return root; } /* Otherwise, recur down the tree */ if (key < root.key) root.left = insertRec(root.left, key); else if (key > root.key) root.right = insertRec(root.right, key); /* return the root */ return root; } // A function to do // inorder traversal of BST void inorderRec(Node root) { if (root != null ) { inorderRec(root.left); Console.Write(root.key + " " ); inorderRec(root.right); } } void treeins( int []arr) { for ( int i = 0; i < arr.Length; i++) { insert(arr[i]); } } // Driver Code public static void Main(String[] args) { GFG tree = new GFG(); int []arr = {5, 4, 7, 2, 11}; tree.treeins(arr); tree.inorderRec(tree.root); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript program to // implement Tree Sort // Class containing left and // right child of current // node and key value class Node { constructor(item) { this .key = item; this .left = this .right = null ; } } // Root of BST let root = new Node(); root = null ; // This method mainly // calls insertRec() function insert(key) { root = insertRec(root, key); } /* A recursive function to insert a new key in BST */ function insertRec(root, key) { /* If the tree is empty, return a new node */ if (root == null ) { root = new Node(key); return root; } /* Otherwise, recur down the tree */ if (key < root.key) root.left = insertRec(root.left, key); else if (key > root.key) root.right = insertRec(root.right, key); /* return the root */ return root; } // A function to do // inorder traversal of BST function inorderRec(root) { if (root != null ) { inorderRec(root.left); document.write(root.key + " " ); inorderRec(root.right); } } function treeins(arr) { for (let i = 0; i < arr.length; i++) { insert(arr[i]); } } // Driver Code let arr = [5, 4, 7, 2, 11]; treeins(arr); inorderRec(root); // This code is contributed // by Saurabh Jaiswal </script> |
2 4 5 7 11
Complexity Analysis:
Average Case Time Complexity: O(n log n) Adding one item to a Binary Search tree on average takes O(log n) time. Therefore, adding n items will take O(n log n) time
Worst Case Time Complexity: O(n2). The worst case time complexity of Tree Sort can be improved by using a self-balancing binary search tree like Red Black Tree, AVL Tree. Using self-balancing binary tree Tree Sort will take O(n log n) time to sort the array in worst case.
Auxiliary Space: O(n)
Contact Us