Sorting is a core concept in programming, helping developers organize data efficiently for easy retrieval and analysis. One interesting and practical sorting technique is Tree Sort, which uses a Binary Search Tree (BST) to arrange elements in order. Unlike simpler sorting algorithms like Bubble Sort or Selection Sort, Tree Sort leverages the hierarchical structure of a BST to achieve efficient sorting while naturally maintaining order. This makes it a great way for beginners to understand both sorting and tree data structures simultaneously.
with hands-on learning.
get the skills and confidence to land your next move.
Java, being a versatile and widely-used programming language, provides a perfect platform to implement Tree Sort. By learning Tree Sort in Java, beginners not only strengthen their algorithmic thinking but also gain valuable experience with object-oriented programming. In this article, we will explore multiple ways to implement Tree Sort in Java, from recursive insertion to iterative methods, handling duplicates, and even class-based designs. By the end, you’ll have several working examples and a solid understanding of how Tree Sort works.
Program 1: Basic Tree Sort Implementation Using Binary Search Tree
This program demonstrates how to implement Tree Sort using a simple Binary Search Tree. Each element from the array is inserted into the tree, and an in-order traversal retrieves the elements in ascending order.
public class TreeSortExample {
public static void treeSort(int[] arr) {
BinarySearchTree bst = new BinarySearchTree();
for (int num : arr) {
bst.insert(num);
}
int[] index = {0};
bst.inorderTraversal(bst.root, arr, index);
}
public static void main(String[] args) {
int[] arr = {5, 2, 8, 1, 3, 7};
System.out.println("Original Array:");
for (int num : arr) System.out.print(num + " ");
System.out.println();
treeSort(arr);
System.out.println("Sorted Array:");
for (int num : arr) System.out.print(num + " ");
}
}
class Node {
int data;
Node left, right;
public Node(int item) {
data = item;
left = right = null;
}
}
class BinarySearchTree {
Node root;
void insert(int key) {
root = insertRec(root, key);
}
Node insertRec(Node root, int key) {
if (root == null) {
root = new Node(key);
return root;
}
if (key < root.data)
root.left = insertRec(root.left, key);
else if (key > root.data)
root.right = insertRec(root.right, key);
return root;
}
void inorderTraversal(Node root, int[] arr, int[] index) {
if (root != null) {
inorderTraversal(root.left, arr, index);
arr[index[0]++] = root.data;
inorderTraversal(root.right, arr, index);
}
}
}In this program, each element is inserted into a BST, which automatically organizes elements such that all left children are smaller and all right children are larger than the parent. An in-order traversal visits the nodes in ascending order. Beginners can see how Tree Sort combines the logic of trees with sorting to achieve efficient ordering.
Program 2: Tree Sort Using Iterative Insertion
Instead of recursion, Tree Sort can also be implemented using iterative insertion. This approach avoids deep recursive calls and is useful for larger datasets.
public class TreeSortExample2 {
static Node insertIterative(Node root, int data) {
Node newNode = new Node(data);
if (root == null) return newNode;
Node current = root;
Node parent = null;
while (current != null) {
parent = current;
if (data < current.data) current = current.left;
else current = current.right;
}
if (data < parent.data) parent.left = newNode;
else parent.right = newNode;
return root;
}
static void inorder(Node root, int[] arr, int[] index) {
if (root != null) {
inorder(root.left, arr, index);
arr[index[0]++] = root.data;
inorder(root.right, arr, index);
}
}
static void treeSort(int[] arr) {
Node root = null;
for (int num : arr) root = insertIterative(root, num);
int[] index = {0};
inorder(root, arr, index);
}
public static void main(String[] args) {
int[] numbers = {7, 3, 8, 4, 2, 6};
System.out.println("Original Array:");
for (int num : numbers) System.out.print(num + " ");
treeSort(numbers);
System.out.println("\nSorted Array:");
for (int num : numbers) System.out.print(num + " ");
}
}
class Node {
int data;
Node left, right;
Node(int data) {
this.data = data;
left = right = null;
}
}Iterative insertion helps beginners understand how BSTs can be navigated without recursion. It’s especially useful when dealing with large arrays that could cause stack overflow with deep recursion.
Program 3: Tree Sort Using Recursion with Helper Function
This version demonstrates Tree Sort in a slightly different style by using recursive helper functions for insertion and traversal. It emphasizes clean separation between tree operations and array manipulation.
import java.util.ArrayList;
public class RecursiveTreeSort {
public static TreeNode insert(TreeNode root, int key) {
if (root == null)
return new TreeNode(key);
if (key < root.data)
root.left = insert(root.left, key);
else
root.right = insert(root.right, key);
return root;
}
public static void inorder(TreeNode root, ArrayList<Integer> result) {
if (root != null) {
inorder(root.left, result);
result.add(root.data);
inorder(root.right, result);
}
}
public static void treeSort(int[] arr) {
TreeNode root = null;
for (int num : arr) {
root = insert(root, num);
}
ArrayList<Integer> sortedList = new ArrayList<>();
inorder(root, sortedList);
for (int i = 0; i < arr.length; i++) {
arr[i] = sortedList.get(i);
}
}
public static void main(String[] args) {
int[] arr = {10, 4, 7, 2, 9, 1};
System.out.println("Original Array:");
for (int num : arr) System.out.print(num + " ");
System.out.println();
treeSort(arr);
System.out.println("Sorted Array:");
for (int num : arr) System.out.print(num + " ");
}
}
class TreeNode {
int data;
TreeNode left, right;
TreeNode(int data) {
this.data = data;
left = right = null;
}
}This recursive approach highlights how recursion can simplify tree operations like insertion and traversal. Beginners can understand the logical flow easily, seeing how elements move from the array into the tree and back into a sorted array.
Program 4: Tree Sort With Duplicate Handling
Tree Sort can handle duplicates efficiently by adding a count property to each node. This ensures repeated elements are sorted correctly.
public class TreeSortExample4 {
static Node insert(Node root, int data) {
if (root == null) return new Node(data);
if (data == root.data) root.count++;
else if (data < root.data) root.left = insert(root.left, data);
else root.right = insert(root.right, data);
return root;
}
static void inorder(Node root, int[] arr, int[] index) {
if (root != null) {
inorder(root.left, arr, index);
for (int i = 0; i < root.count; i++) arr[index[0]++] = root.data;
inorder(root.right, arr, index);
}
}
static void treeSort(int[] arr) {
Node root = null;
for (int num : arr) root = insert(root, num);
int[] index = {0};
inorder(root, arr, index);
}
public static void main(String[] args) {
int[] numbers = {5, 2, 5, 1, 9, 2};
System.out.println("Original Array:");
for (int num : numbers) System.out.print(num + " ");
treeSort(numbers);
System.out.println("\nSorted Array:");
for (int num : numbers) System.out.print(num + " ");
}
}
class Node {
int data, count;
Node left, right;
Node(int data) {
this.data = data;
count = 1;
left = right = null;
}
}By keeping a count in each node, duplicates are efficiently handled. Beginners learn how BSTs can store additional information while still maintaining sorting properties.
Program 5: Tree Sort Using a Class-Based Approach
This approach wraps the BST logic and sorting process in a class, demonstrating object-oriented programming principles.
public class TreeSortExample5 {
public static void main(String[] args) {
int[] numbers = {7, 3, 5, 2, 9, 1};
System.out.println("Original Array:");
for (int num : numbers) System.out.print(num + " ");
BST bst = new BST();
int[] sorted = bst.treeSort(numbers);
System.out.println("\nSorted Array:");
for (int num : sorted) System.out.print(num + " ");
}
}
class BST {
class Node {
int data;
Node left, right;
Node(int data) { this.data = data; }
}
Node root;
void insert(int data) { root = insertRec(root, data); }
Node insertRec(Node node, int data) {
if (node == null) return new Node(data);
if (data < node.data) node.left = insertRec(node.left, data);
else node.right = insertRec(node.right, data);
return node;
}
void inorderTraversal(Node node, int[] arr, int[] index) {
if (node != null) {
inorderTraversal(node.left, arr, index);
arr[index[0]++] = node.data;
inorderTraversal(node.right, arr, index);
}
}
int[] treeSort(int[] arr) {
for (int num : arr) insert(num);
int[] sorted = new int[arr.length];
int[] index = {0};
inorderTraversal(root, sorted, index);
return sorted;
}
}This design demonstrates modularity and clean structure, making it easy for beginners to extend or modify the BST while understanding both sorting and object-oriented design.
Program 6: Using Java’s TreeSet for Tree Sort
Java provides a built-in TreeSet class, which is a self-balancing tree that stores unique elements in sorted order. This program demonstrates a practical and easy way to implement Tree Sort using TreeSet.
import java.util.Arrays;
import java.util.TreeSet;
public class TreeSetSortExample {
public static void main(String[] args) {
int[] arr = {5, 2, 8, 1, 3, 7};
System.out.println("Original Array:");
System.out.println(Arrays.toString(arr));
TreeSet<Integer> treeSet = new TreeSet<>();
for (int num : arr) treeSet.add(num);
int index = 0;
for (int num : treeSet) arr[index++] = num;
System.out.println("Sorted Array:");
System.out.println(Arrays.toString(arr));
}
}Using TreeSet, we can achieve Tree Sort in just a few lines. TreeSet automatically maintains sorted order as elements are added. Beginners can see a real-world example of how Java’s collections make tree-based sorting accessible without implementing the BST manually.
Frequently Asked Questions (FAQ)
Tree Sort often raises questions for beginners. Here are some common answers.
Q1: What is Tree Sort and why is it useful?
Tree Sort uses a Binary Search Tree to organize elements, providing efficient sorting while maintaining a hierarchical structure.
Q2: Can Tree Sort handle duplicate elements?
Yes. By adding a count to each node or handling duplicates during insertion, repeated elements are sorted correctly.
Q3: How does Tree Sort compare to Quick Sort or Merge Sort?
Tree Sort has an average time complexity of O(n log n), similar to Quick Sort or Merge Sort. However, its performance depends on tree balance, as an unbalanced tree can degrade to O(n²).
Q4: Can Tree Sort be implemented without recursion?
Yes. Iterative insertion and traversal methods allow Tree Sort to function without recursion, preventing stack overflow on large datasets.
Q5: Where is Tree Sort commonly used?
Tree Sort is ideal when data naturally fits a tree structure, when duplicates need careful handling, or when you want to sort while building a searchable tree.
Conclusion
Tree Sort is a versatile and efficient algorithm that combines sorting with tree data structures. In Java, it can be implemented recursively, iteratively, with duplicate handling, or through object-oriented approaches. Each example helps beginners understand how BSTs organize data, making sorting efficient and structured.
By practicing these programs, beginners can improve their Java programming skills, gain confidence with recursion and classes, and see how data structures like trees can directly influence algorithm performance. Tree Sort is not just a sorting algorithm—it’s a step into the world of structured data and intelligent data organization.
