Tree Sort Java Program

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-

1. Using the elements in an input array create a Binary search tree.
2. 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 means the worst case time complexity of tree sort is O(n²).

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).

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

• Shell Sort Java Program
• Java String repeat() Method
• How to List All The Files in a Directory in Java
• Java Exception Handling Best Practices
• static in Java With Examples
• Java Immutable List With Examples
• First React App – Hello World React Example
• Spring Boot Stand Alone (non web) Application Example