Tutorialspoint.dev

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.



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 inoder 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++)
        insert(root, arr[i]);
  
    // Store inoder 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


Output:

2 4 5 7 11

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)

References:
https://en.wikipedia.org/wiki/Tree_sort

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter