Tree Sort Using Binary Search Tree in Java

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-

A Node class representing a node in the binary search tree. This class can be written as an internal class

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.
A method to traverse the tree in in-order which gives us elements in sorted order.

Below is the complete source code:

package com.kkjavatutorials.tree;

public class BinarySearchTree {

	public Node node;
	
	public BinarySearchTree(int data) {
		this.node = new Node(data);
	}

	public Node insert(Node node,int data) {
		if(node == null) {
			return new Node(data);
		}
		
		if(data < node.data) {
			node.left = insert(node.left, data);
		}
		
		else if(data > node.data) {
			node.right = insert(node.right, data);
		}
		return node;
	}

	public void inOrder(Node node) {
		if(node != null) {
			inOrder(node.left);
			System.out.print(node.data+" ");
			inOrder(node.right);
		}
	}
	
	class Node{
	
		private int data;
		private Node left;
		private Node right;
		public Node(int data) {
			super();
			this.data = data;
			this.left = null;
			this.right = null;
		}
	}
}

package com.kkjavatutorials.tree;

public class BinarySearchTree {

public Node node;

public BinarySearchTree(int data) {

this.node = new Node(data);

}

public Node insert(Node node,int data) {

if(node == null) {

return new Node(data);

}

if(data < node.data) {

node.left = insert(node.left, data);

}

else if(data > node.data) {

node.right = insert(node.right, data);

}

return node;

}

public void inOrder(Node node) {

if(node != null) {

inOrder(node.left);

System.out.print(node.data+" ");

inOrder(node.right);

}

class Node{

private int data;

private Node left;

private Node right;

public Node(int data) {

super();

this.data = data;

this.left = null;

this.right = null;

}

Client Program

package com.kkjavatutorials.client;

import java.util.Arrays;

import com.kkjavatutorials.tree.BinarySearchTree;

public class BinarySearchTreeTest {

	public static void main(String[] args) {

		int[] intputArrayElements = {100,10,20,30,120,110,105};
		 
		System.out.println("Original Array::"+Arrays.toString(intputArrayElements));
		
		BinarySearchTree binarySearchTree = new BinarySearchTree(intputArrayElements[0]);
		
		for (int data : intputArrayElements) {
			binarySearchTree.insert(binarySearchTree.node, data);
		}
		System.out.print("After sorting::");
		
		binarySearchTree.inOrder(binarySearchTree.node);
		
	}
}

package com.kkjavatutorials.client;

import java.util.Arrays;

import com.kkjavatutorials.tree.BinarySearchTree;

public class BinarySearchTreeTest {

public static void main(String[] args) {

int[] intputArrayElements = {100,10,20,30,120,110,105};

System.out.println("Original Array::"+Arrays.toString(intputArrayElements));

BinarySearchTree binarySearchTree = new BinarySearchTree(intputArrayElements[0]);

for (int data : intputArrayElements) {

binarySearchTree.insert(binarySearchTree.node, data);

}

System.out.print("After sorting::");

binarySearchTree.inOrder(binarySearchTree.node);

}

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:

Introduction to Hibernate 5
Latest hibernate distribution Zip file download link
Hibernate 5 distribution binary details
Create SessionFactory in Hibernate5 using hibernate.cfg.xml
Create SessionFactory in Hibernate5 without hibernate.cfg.xml
Save and persist an entity example in hibernate
Hibernate CRUD(Create,Read,Update and Delete) example
Dirty checking in hibernate example
Understanding hibernate Configuration File
Why to use hibernate dialect?
Hibernate hbm2ddl property
What are the benefits of using hibernate?

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.

Leave a Reply Cancel reply