Sorting is a fundamental task in programming, and understanding different sorting algorithms can make your code more efficient and flexible. One interesting algorithm that combines sorting and data structures is Tree Sort. Unlike typical comparison-based sorts like bubble sort or merge sort, Tree Sort uses a Binary Search Tree (BST) to organize data. This makes the algorithm not only a method of sorting but also a great way to practice using trees, which are essential in computer science.
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 BST, which automatically places smaller elements to the left and larger elements to the right. Then, an in-order traversal of the tree retrieves the elements in sorted order. This algorithm is useful when you need both sorting and fast search operations because the BST structure allows for efficient lookups. Beginners can benefit from Tree Sort as it introduces the concept of combining data structures with algorithms in a practical way.
Program 1: Basic Tree Sort Using Recursion
This program shows the standard approach to Tree Sort. It inserts elements into a BST and performs an in-order traversal to produce a sorted array.
#include <iostream>
using namespace std;
// Node structure for BST
struct Node {
int data;
Node* left;
Node* right;
Node(int val) {
data = val;
left = right = nullptr;
}
};
// Insert node into BST
Node* insert(Node* root, int val) {
if (!root) return new Node(val);
if (val < root->data)
root->left = insert(root->left, val);
else
root->right = insert(root->right, val);
return root;
}
// In-order traversal to print sorted elements
void inOrderTraversal(Node* root) {
if (!root) return;
inOrderTraversal(root->left);
cout << root->data << " ";
inOrderTraversal(root->right);
}
int main() {
int arr[] {5, 2, 9, 1, 6, 3};
int n = sizeof(arr) / sizeof(arr[0]);
Node* root = nullptr;
for (int i = 0; i < n; i++)
root = insert(root, arr[i]);
cout << "Sorted array using Tree Sort: ";
inOrderTraversal(root);
cout << endl;
return 0;
}In this program, elements are inserted into a BST one by one. The in-order traversal visits nodes in ascending order, effectively sorting the array. This approach is simple and helps beginners understand how trees can naturally organize data.
Program 2: Tree Sort with Array Output
This version of Tree Sort collects the sorted elements into a separate array instead of printing them directly. This is useful when you want to reuse the sorted array in further calculations.
#include <iostream>
#include <vector>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
Node(int val) {
data = val;
left = right = nullptr;
}
};
Node* insert(Node* root, int val) {
if (!root) return new Node(val);
if (val < root->data)
root->left = insert(root->left, val);
else
root->right = insert(root->right, val);
return root;
}
// Store in-order traversal in a vector
void inOrderToArray(Node* root, vector<int>& sorted) {
if (!root) return;
inOrderToArray(root->left, sorted);
sorted.push_back(root->data);
inOrderToArray(root->right, sorted);
}
int main() {
int arr[] {8, 3, 7, 1, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
Node* root = nullptr;
for (int i = 0; i < n; i++)
root = insert(root, arr[i]);
vector<int> sorted;
inOrderToArray(root, sorted);
cout << "Sorted array stored in vector: ";
for (int val : sorted)
cout << val << " ";
cout << endl;
return 0;
}By storing the sorted values in a vector, this program demonstrates a practical way to use the sorted data programmatically. Beginners can see how the tree structure supports both sorting and efficient data retrieval.
Program 3: Tree Sort Handling Duplicate Values
Sometimes arrays contain duplicate values, and it’s important that Tree Sort handles them correctly. This version inserts duplicate values to the right, preserving all elements.
#include <iostream>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
Node(int val) {
data = val;
left = right = nullptr;
}
};
Node* insert(Node* root, int val) {
if (!root) return new Node(val);
if (val <= root->data) // duplicates go to left or right consistently
root->left = insert(root->left, val);
else
root->right = insert(root->right, val);
return root;
}
void inOrderTraversal(Node* root) {
if (!root) return;
inOrderTraversal(root->left);
cout << root->data << " ";
inOrderTraversal(root->right);
}
int main() {
int arr[] {4, 2, 4, 1, 3, 2};
int n = sizeof(arr) / sizeof(arr[0]);
Node* root = nullptr;
for (int i = 0; i < n; i++)
root = insert(root, arr[i]);
cout << "Sorted array with duplicates handled: ";
inOrderTraversal(root);
cout << endl;
return 0;
}By consistently inserting duplicates to one side, the tree ensures that all elements are included and in-order traversal still produces a sorted sequence. Beginners learn how small adjustments in insertion logic help manage duplicates gracefully.
Frequently Asked Questions (FAQ)
Here are some common beginner questions about Tree Sort in C++:
Q1: What is Tree Sort?
Tree Sort is a sorting algorithm that uses a Binary Search Tree (BST) to organize elements. An in-order traversal of the tree produces a sorted array.
Q2: Is Tree Sort stable?
Tree Sort is generally not stable because duplicate elements may change their relative order depending on insertion rules.
Q3: What is the time complexity of Tree Sort?
The average case is O(n log n), but the worst case is O(n²) if the tree becomes unbalanced.
Q4: Can Tree Sort handle negative numbers?
Yes, Tree Sort can handle negative numbers since BST comparisons work with all integers.
Q5: Why use Tree Sort instead of other sorting algorithms?
Tree Sort combines sorting and efficient search. It’s useful when you need a sorted structure that also supports fast insertions and lookups.
Conclusion
Tree Sort is a unique sorting algorithm that introduces beginners to Binary Search Trees while producing a sorted array. In this article, we explored multiple implementations: the basic recursive tree sort, storing results in an array, and handling duplicate values. By practicing Tree Sort, beginners can understand how data structures can enhance algorithms, how in-order traversal naturally produces sorted output, and how to manage duplicates efficiently. Tree Sort is both educational and practical, making it a great tool for learning algorithmic thinking with C++.
