Sorting is a fundamental concept in programming, and learning different sorting algorithms helps us understand how data can be efficiently organized. One interesting and powerful sorting technique is Tree Sort, which uses a Binary Search Tree (BST) to sort elements. Unlike traditional comparison-based sorts like Bubble Sort or Quick Sort, Tree Sort leverages the properties of a tree structure, making it efficient for dynamic datasets and helping beginners understand tree traversal concepts.
with hands-on learning.
get the skills and confidence to land your next move.
Tree Sort works by inserting all elements of an array into a Binary Search Tree, and then performing an in-order traversal of the tree. In-order traversal ensures that elements are retrieved in sorted order because, by definition, the left child of a BST node is smaller, and the right child is larger. Tree Sort is useful in scenarios where the dataset needs to be maintained in sorted order dynamically, such as in priority queues or real-time search applications.
Program 1: Basic Tree Sort
This first program shows a simple Tree Sort implementation using loops and recursion for insertion and traversal. It demonstrates the core concept clearly for beginners.
using System;
class Node
{
public int Data;
public Node Left, Right;
public Node(int item)
{
Data = item;
Left = Right = null;
}
}
class Program
{
static Node Insert(Node root, int key)
{
if (root == null)
return new Node(key);
if (key < root.Data)
root.Left = Insert(root.Left, key);
else
root.Right = Insert(root.Right, key);
return root;
}
static void InOrderTraversal(Node root)
{
if (root != null)
{
InOrderTraversal(root.Left);
Console.Write(root.Data + " ");
InOrderTraversal(root.Right);
}
}
static void Main()
{
int[] arr = { 5, 3, 7, 2, 4, 6, 8 };
Node root = null;
foreach (int num in arr)
root = Insert(root, num);
Console.WriteLine("Sorted array using Tree Sort:");
InOrderTraversal(root);
Console.WriteLine();
}
}In this program, each number from the array is inserted into the BST. The in-order traversal ensures the elements are printed in ascending order. Beginners can see how a tree structure can simplify sorting compared to manual element comparisons.
Program 2: Tree Sort with Duplicate Handling
This version adds duplicate handling. It’s useful in real-world datasets where repeated values may appear.
using System;
using System.Collections.Generic;
class Node
{
public int Data;
public Node Left, Right;
public int Count; // Stores number of duplicates
public Node(int item)
{
Data = item;
Left = Right = null;
Count = 1;
}
}
class Program
{
static Node Insert(Node root, int key)
{
if (root == null)
return new Node(key);
if (key == root.Data)
root.Count++;
else if (key < root.Data)
root.Left = Insert(root.Left, key);
else
root.Right = Insert(root.Right, key);
return root;
}
static void InOrderTraversal(Node root)
{
if (root != null)
{
InOrderTraversal(root.Left);
for (int i = 0; i < root.Count; i++)
Console.Write(root.Data + " ");
InOrderTraversal(root.Right);
}
}
static void Main()
{
int[] arr = { 5, 3, 7, 3, 2, 4, 6, 8, 7 };
Node root = null;
foreach (int num in arr)
root = Insert(root, num);
Console.WriteLine("Sorted array with duplicates using Tree Sort:");
InOrderTraversal(root);
Console.WriteLine();
}
}By using a Count variable, duplicates are tracked, ensuring that repeated values appear the correct number of times in the sorted output. This approach makes Tree Sort more practical for real-life data.
Program 3: Iterative Insertion in Tree Sort
Some beginners prefer iterative insertion rather than recursion. This version avoids recursion for inserting elements into the BST.
using System;
class Node
{
public int Data;
public Node Left, Right;
public Node(int item)
{
Data = item;
Left = Right = null;
}
}
class Program
{
static Node InsertIterative(Node root, int key)
{
Node newNode = new Node(key);
if (root == null) return newNode;
Node current = root;
Node parent = null;
while (current != null)
{
parent = current;
if (key < current.Data)
current = current.Left;
else
current = current.Right;
}
if (key < parent.Data)
parent.Left = newNode;
else
parent.Right = newNode;
return root;
}
static void InOrderTraversal(Node root)
{
if (root != null)
{
InOrderTraversal(root.Left);
Console.Write(root.Data + " ");
InOrderTraversal(root.Right);
}
}
static void Main()
{
int[] arr = { 10, 5, 15, 3, 7, 12, 18 };
Node root = null;
foreach (int num in arr)
root = InsertIterative(root, num);
Console.WriteLine("Sorted array using iterative Tree Sort:");
InOrderTraversal(root);
Console.WriteLine();
}
}Iterative insertion is helpful for beginners who want to avoid deep recursion and understand how loops can traverse and insert elements in a BST.
Program 4: Tree Sort Using a Sorted List
This program shows how a BST can be used along with a dynamic list to store sorted elements. It highlights the flexibility of Tree Sort for building other data structures.
using System;
using System.Collections.Generic;
class Node
{
public int Data;
public Node Left, Right;
public Node(int item)
{
Data = item;
Left = Right = null;
}
}
class Program
{
static Node Insert(Node root, int key)
{
if (root == null) return new Node(key);
if (key < root.Data)
root.Left = Insert(root.Left, key);
else
root.Right = Insert(root.Right, key);
return root;
}
static void InOrderTraversal(Node root, List<int> sortedList)
{
if (root != null)
{
InOrderTraversal(root.Left, sortedList);
sortedList.Add(root.Data);
InOrderTraversal(root.Right, sortedList);
}
}
static void Main()
{
int[] arr = { 20, 10, 30, 5, 15, 25, 35 };
Node root = null;
foreach (int num in arr)
root = Insert(root, num);
List<int> sorted = new List<int>();
InOrderTraversal(root, sorted);
Console.WriteLine("Sorted array stored in a list using Tree Sort:");
foreach (int num in sorted)
Console.Write(num + " ");
Console.WriteLine();
}
}This approach shows how Tree Sort can output sorted data into another structure, making it adaptable for applications requiring lists or arrays after sorting.
Frequently Asked Questions (FAQ)
Tree Sort often raises questions for beginners. Here are some answers:
Q1: Is Tree Sort faster than Quick Sort?
It depends. On average, Tree Sort has O(n log n) complexity if the tree is balanced. Quick Sort is faster in practice for arrays because it avoids tree overhead.
Q2: Can Tree Sort handle duplicate numbers?
Yes, using a Count variable in nodes, duplicates can be correctly handled.
Q3: Is Tree Sort stable?
Tree Sort is generally not stable unless a modification is made to maintain the order of equal elements.
Q4: What happens if the BST becomes unbalanced?
If the BST becomes skewed, the time complexity can degrade to O(n²), similar to Quick Sort in its worst case.
Conclusion
Tree Sort is an elegant and educational sorting algorithm that leverages the Binary Search Tree to organize data efficiently. It introduces beginners to important concepts like tree insertion, traversal, and handling duplicates. By experimenting with recursive, iterative, and list-based variations, learners can gain a deeper understanding of both sorting and tree data structures. Practicing Tree Sort helps build a strong foundation for advanced algorithms like AVL Trees, Red-Black Trees, and other data structure applications.
