Sorting is a fundamental concept in computer science. It helps us organize data in a meaningful way so we can easily search, analyze, and make decisions. Whether you are sorting numbers, words, or even records, sorting algorithms make everything faster and more efficient. One interesting sorting method that connects sorting with data structures is Tree Sort.
with hands-on learning.
get the skills and confidence to land your next move.
Tree Sort is a unique algorithm that uses the properties of a Binary Search Tree (BST) to sort data. The concept is simple yet elegant — first, we insert all elements of the array into a binary search tree, and then we perform an in-order traversal of the tree to retrieve the elements in sorted order. This makes Tree Sort a great learning tool for beginners who want to understand both sorting and trees in C programming. It’s often used when we want to maintain data in a structure that supports both fast insertion and sorted retrieval, such as in databases or hierarchical data systems.
Program 1: Basic Tree Sort Using Recursion
The first version of Tree Sort uses recursion, which is the most common and clear way to understand how the algorithm works. This version builds a binary search tree and then traverses it in order to produce sorted output.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *left, *right;
};
struct Node* newNode(int value) {
struct Node* node = (struct Node*) malloc(sizeof(struct Node));
node->data = value;
node->left = node->right = NULL;
return node;
}
struct Node* insert(struct Node* root, int value) {
if (root == NULL)
return newNode(value);
if (value < root->data)
root->left = insert(root->left, value);
else
root->right = insert(root->right, value);
return root;
}
void inOrderTraversal(struct Node* root) {
if (root != NULL) {
inOrderTraversal(root->left);
printf("%d ", root->data);
inOrderTraversal(root->right);
}
}
void treeSort(int arr[], int n) {
struct Node* root = NULL;
root = insert(root, arr[0]);
for (int i = 1; i < n; i++)
insert(root, arr[i]);
inOrderTraversal(root);
}
int main() {
int arr[] = {5, 2, 9, 1, 3, 7};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array:\n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
printf("Sorted array:\n");
treeSort(arr, n);
printf("\n");
return 0;
}In this program, we first define a structure for the tree node. Each node contains a data value and pointers to its left and right child. The insert() function places elements into the binary search tree, ensuring that smaller values go to the left and larger values go to the right. After the tree is built, the inOrderTraversal() function visits nodes in ascending order, effectively sorting the data. This recursive approach is clean and easy to follow, making it perfect for beginners learning about trees and recursion in C.
Program 2: Tree Sort Without Recursion (Using Loops and Stack Simulation)
While recursion makes Tree Sort elegant, it’s also possible to implement it using loops and a manual stack structure. This can be helpful when recursion depth is a concern or when a beginner wants to practice iterative problem-solving.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *left, *right;
};
struct Node* newNode(int value) {
struct Node* node = (struct Node*) malloc(sizeof(struct Node));
node->data = value;
node->left = node->right = NULL;
return node;
}
struct Node* insert(struct Node* root, int value) {
struct Node* newnode = newNode(value);
struct Node* current = root;
struct Node* parent = NULL;
if (root == NULL)
return newnode;
while (current != NULL) {
parent = current;
if (value < current->data)
current = current->left;
else
current = current->right;
}
if (value < parent->data)
parent->left = newnode;
else
parent->right = newnode;
return root;
}
void inOrderIterative(struct Node* root) {
struct Node* stack[100];
int top = -1;
struct Node* current = root;
while (current != NULL || top != -1) {
while (current != NULL) {
stack[++top] = current;
current = current->left;
}
current = stack[top--];
printf("%d ", current->data);
current = current->right;
}
}
void treeSort(int arr[], int n) {
struct Node* root = NULL;
root = insert(root, arr[0]);
for (int i = 1; i < n; i++)
insert(root, arr[i]);
inOrderIterative(root);
}
int main() {
int arr[] = {8, 4, 2, 10, 9, 7, 3};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array:\n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
printf("Sorted array:\n");
treeSort(arr, n);
printf("\n");
return 0;
}Here, instead of using recursion, we simulate the function call stack manually using an array. This iterative method helps beginners visualize how recursion works behind the scenes. The logic remains the same — build the binary search tree, then traverse it in order. This version gives a clearer understanding of how data is stored and processed step by step, which can be very educational for new C programmers.
Program 3: Tree Sort That Handles User Input
In this version, we make the program interactive. The user can enter any number of elements, and the program will use Tree Sort to arrange them in ascending order.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *left, *right;
};
struct Node* newNode(int value) {
struct Node* node = (struct Node*) malloc(sizeof(struct Node));
node->data = value;
node->left = node->right = NULL;
return node;
}
struct Node* insert(struct Node* root, int value) {
if (root == NULL)
return newNode(value);
if (value < root->data)
root->left = insert(root->left, value);
else
root->right = insert(root->right, value);
return root;
}
void inOrderTraversal(struct Node* root) {
if (root != NULL) {
inOrderTraversal(root->left);
printf("%d ", root->data);
inOrderTraversal(root->right);
}
}
void treeSort(int arr[], int n) {
struct Node* root = NULL;
for (int i = 0; i < n; i++)
root = insert(root, arr[i]);
inOrderTraversal(root);
}
int main() {
int n;
printf("Enter the number of elements: ");
scanf("%d", &n);
int arr[n];
printf("Enter %d elements:\n", n);
for (int i = 0; i < n; i++)
scanf("%d", &arr[i]);
printf("Sorted array:\n");
treeSort(arr, n);
printf("\n");
return 0;
}This version helps beginners experiment with their own data instead of relying on fixed arrays. By inserting custom numbers, learners can see how Tree Sort performs across different inputs and sizes. It also strengthens understanding of dynamic data structures in C, as every insertion dynamically allocates memory for new nodes.
Frequently Asked Questions (FAQ)
This section answers a few common questions that beginners often ask while learning Tree Sort in C.
What is the main idea behind Tree Sort?
Tree Sort is based on building a Binary Search Tree from the elements of an array and then performing an in-order traversal to output them in sorted order.
Is Tree Sort faster than Bubble Sort or Insertion Sort?
Yes, Tree Sort generally performs better than Bubble or Insertion Sort for larger datasets. The average time complexity is O(n log n), but in the worst case (for already sorted input), it can degrade to O(n²) if the tree becomes unbalanced.
Can Tree Sort handle negative numbers?
Absolutely! The algorithm compares values directly, so it can handle both positive and negative integers without any changes.
Why use Tree Sort if there are faster algorithms like Quick Sort?
Tree Sort is particularly useful for learning purposes. It helps students understand both sorting logic and binary trees at the same time. It’s also handy when you want a data structure that keeps elements sorted dynamically, like in some database operations.
Conclusion
Tree Sort beautifully combines the concepts of sorting and binary search trees, offering both an educational and practical approach to arranging data. While it might not always be the fastest method in every situation, its logical clarity and step-by-step structure make it an ideal choice for beginners who want to understand how sorting can be achieved through data structures.
By practicing different versions — recursive, iterative, and user-driven — learners can gain a deeper appreciation for how data flows through a tree and how in-order traversal results in sorted output. Keep experimenting with this algorithm, modify it, and observe how trees grow and behave. The more you play with it, the clearer and more enjoyable C programming becomes!
