# Tree Sort Using Binary Search Tree in Java

By | June 11, 2020

Hello Friends,
In this post, we will talk and learn about Tree Sort Using Binary Search Tree in Java?

Tree sort sorting algorithm that uses basically the Binary Search tree data structure for sorting.

Binary Search tree

Binary Search Tree or BST is a node-based binary tree data structure which are having the following properties:

• The left subtree of a node contains only nodes with values smaller value than the current node’s value.
• The right subtree of a node contains only nodes with values greater than the current node’s value.
• The left and right subtrees are also must be a binary search tree.
• You should note that Binary Search Tree (BST) must not be duplicate nodes. To write a Tree sort We have to follow the below steps.

First of all, we have to create a Binary search tree (BST) from the input array.

Once we convert input array in BST then we have to do an in-order traversal, which means we have to start from the left subtree then the root node and then visit the right subtree, we can get the elements sorted in ascending order.

If we traverse in reverse order i.e. first visit the right subtree, then the root node and then the left subtree we can get the elements sorted in descending order.

To write a program for Tree sort we need-

1. A Node class representing a node in the binary search tree. This class can be written as an internal class
1. A method to insert nodes in a Binary search tree (BST). The logic for inserting a new node in the Binary search tree has to implement as follows:
• If a new node’s value is less than the current node moves to the left.
• If a new node’s value is greater than the current node moves to the right.
• When the current node is null that means leaf, node is reached. A new node should be inserted in that position.
2. A method to traverse the tree in in-order which gives us elements in sorted order.

Below is the complete source code:

Client Program

The output of the above client program:

Original Array::[100, 10, 20, 30, 120, 110, 105]
After sorting::10 20 30 100 105 110 120

Performance of tree sort:

The average time complexity of tree sort is O(n log n), To insert an element in the Binary search tree takes O(log n) time so for n elements it is O(n log n).

The space complexity of tree sort is O(n) as we have to create n nodes for n elements.

You May Also Like:

That’s all about How to Write a Java program for Tree Sort Using Binary Search Tree in Java?
If you have any feedback or suggestion please feel free to drop in below comment box.