This tutorial shows how to write Tree sort program in Java. Tree sort uses a Binary Search Tree (BST) for sorting the elements.

#### What is a Binary Search Tree

Binary Search Tree (BST) is a special kind of binary tree where node’s left child has a value less than its parent node and the node’s right child has a value greater than or equal to its parent node.

Following image shows a Binary search tree with nodes. As you can see left subtree has nodes with values less than the root node and the right subtree has nodes with values greater than the root node.

#### Tree Sort Algorithm

Tree sort work as follows-

- Using the elements in an input array create a Binary search tree.
- Do an in-order traversal of the BST to get elements in sorted order. In order traversal is done by first visiting the left subtree nodes then root node and then the right subtree nodes.

#### Tree Sort Java Program

To represent a BST node a node class is required which has two references to itself. These references refer to left child and right child respectively.This Node class is used to create nodes of BST.

class Node{ int value; Node left; Node right; Node(int value){ this.value = value; left = null; right = null; } }

**Tree Sort**

// Class for tree nodes class Node{ int value; Node left; Node right; Node(int value){ this.value = value; left = null; right = null; } } // Class for Binary Search Tree class BST{ Node node; BST(int value){ node = new Node(value); } public Node insert(Node node, int value){ if(node == null){ return new Node(value); } // Move to left for value less than parent node if(value < node.value){ node.left = insert(node.left, value); } // Move to right for value greater than parent node else if(value > node.value){ node.right = insert(node.right, value); } return node; } // For traversing in order public void inOrder(Node node){ if(node != null){ // recursively traverse left subtree inOrder(node.left); System.out.print(node.value + " "); // recursively traverse right subtree inOrder(node.right); } } } public class TreeSort { public static void main(String[] args) { int[] arr = {65, 68, 82, 42, 10, 75, 25, 47, 32, 72}; System.out.println("Original array- " + Arrays.toString(arr)); // start creating tree with element at index 0 as root node BST bst = new BST(arr[0]); for(int num : arr){ bst.insert(bst.node, num); } System.out.print("Sorted Array after Tree sort- "); bst.inOrder(bst.node); System.out.println(); } }

__Output__

Original array- [65, 68, 82, 42, 10, 75, 25, 47, 32, 72] Sorted Array after Tree sort- 10 25 32 42 47 65 68 72 75 82

#### Tree Sort time and space complexity

Average case time complexity of Tree sort is **O(n logn)**.

If the tree is an unbalanced binary tree, adding an item requires O(n) time in the worst-case. This the worst case time complexity of tree sort is **O(n ^{2})**.

Since n number of nodes are to be created for n elements thus auxiliary space requirement is n. So, the space complexity of tree sort is **O(n)**.

**Related Posts**

- Heap Sort Java Program
- Merge Sort Java Program
- Shell Sort Java Program
- Quick Sort Java Program
- Bubble Sort Java Program
- Selection Sort Java Program
- How to Make a File or Folder Hidden in Java
- Java Program to Check if Armstrong Number

That’s all for the topic **Tree Sort Java Program**. If something is missing or you have something to share about the topic please write a comment.

**You may also like**