Tree Sort is an elegant sorting algorithm that uses a special data structure called a binary search tree (BST) to sort numbers efficiently. Unlike simpler sorting methods like bubble sort or insertion sort, Tree Sort organizes data in a tree where each node has a value and two children. Values smaller than a node go to the left child, and values larger go to the right. This makes searching, inserting, and sorting the elements very structured and fast.
with hands-on learning.
get the skills and confidence to land your next move.
For beginners in Perl, Tree Sort is a great way to see how data structures like trees can be applied to solve practical problems. It is often used in situations where we want both sorting and quick searches, like in database indexing, or when organizing large datasets where speed matters. By learning Tree Sort, you not only understand sorting but also how trees work in programming.
Program 1: Basic Tree Sort using recursion
This first program demonstrates a simple Tree Sort in Perl. It builds a binary search tree from predefined data and then traverses it in order to get a sorted array.
use strict;
use warnings;
# ----------------------
# Node package (BST node)
# ----------------------
package Node;
# Constructor: create a new node
sub new {
my ($class, $value) = @_;
return bless { value => $value, left => undef, right => undef }, $class;
}
# Insert a value into the BST
sub insert {
my ($node, $value) = @_;
return Node->new($value) unless $node;
if ($value < $node->{value}) {
$node->{left} = insert($node->{left}, $value);
} else {
$node->{right} = insert($node->{right}, $value);
}
return $node;
}
# In-order traversal: left, root, right
sub inorder {
my ($node, $arr) = @_;
return unless $node;
inorder($node->{left}, $arr);
push @$arr, $node->{value};
inorder($node->{right}, $arr);
}
# ----------------------
# Main program
# ----------------------
package main;
my @arr = (50, 30, 20, 40, 70, 60, 80);
# Insert into BST
my $root;
$root = Node::insert($root, $_) for @arr;
# In-order traversal
my @sorted;
Node::inorder($root, \@sorted);
print "Sorted array: @sorted\n";This program works by first inserting all elements into the binary search tree, respecting the BST property. Then, an in-order traversal reads the values in ascending order. Beginners can understand this as “building a tree and walking through it carefully” to get a sorted list.
Program 2: Tree Sort with clearer function separation
In this version, insertion and traversal are separated more clearly to make it easier for beginners to follow. The logic is the same but written in a way that reads like a story.
use strict;
use warnings;
# ----------------------
# Node package (BST node)
# ----------------------
package Node;
# Constructor: create a new node
sub new {
my ($class, $value) = @_;
return bless { value => $value, left => undef, right => undef }, $class;
}
# Insert a value into the BST
sub insert {
my ($node, $value) = @_;
# If current node is empty, create new node
return Node->new($value) unless $node;
# Recursively insert into left or right subtree
$node->{left} = insert($node->{left}, $value) if $value < $node->{value};
$node->{right} = insert($node->{right}, $value) if $value >= $node->{value};
return $node;
}
# In-order traversal (left, root, right)
# Fills array with sorted values
sub inorder_traversal {
my ($node, $arr) = @_;
return unless $node;
inorder_traversal($node->{left}, $arr);
push @$arr, $node->{value};
inorder_traversal($node->{right}, $arr);
}
# ----------------------
# Main program
# ----------------------
package main;
# Array to sort
my @arr = (15, 10, 20, 8, 12, 17, 25);
# Build BST
my $root;
$root = Node::insert($root, $_) for @arr;
# Traverse BST to get sorted array
my @sorted;
Node::inorder_traversal($root, \@sorted);
# Print result
print "Sorted array: @sorted\n";Here, beginners can follow a step-by-step flow: insert values into the tree, then traverse it in order to get the sorted result. This version emphasizes readability and clear separation of tasks.
Program 3: Tree Sort handling duplicate values
This program shows how to handle duplicates in Tree Sort. Duplicates are inserted into the right subtree, keeping the sort stable for repeated numbers.
use strict;
use warnings;
# ----------------------
# Node package (BST node)
# ----------------------
package Node;
# Constructor: create a new BST node
sub new {
my ($class, $value) = @_;
return bless { value => $value, left => undef, right => undef }, $class;
}
# Insert a value into BST
sub insert {
my ($node, $value) = @_;
return Node->new($value) unless $node;
if ($value <= $node->{value}) {
# Insert into left subtree
$node->{left} = insert($node->{left}, $value);
} else {
# Insert into right subtree
$node->{right} = insert($node->{right}, $value);
}
return $node;
}
# In-order traversal to get sorted array
sub inorder {
my ($node, $arr) = @_;
return unless $node;
inorder($node->{left}, $arr);
push @$arr, $node->{value};
inorder($node->{right}, $arr);
}
# ----------------------
# Main program
# ----------------------
package main;
# Array to sort (duplicates included)
my @arr = (10, 5, 15, 10, 20, 5, 25);
# Build BST
my $root;
$root = Node::insert($root, $_) for @arr;
# Traverse BST in-order to get sorted array
my @sorted;
Node::inorder($root, \@sorted);
# Print the sorted array
print "Sorted array: @sorted\n";Handling duplicates correctly ensures that Tree Sort remains stable. Beginners can observe how equal numbers are placed in the tree while preserving order, which is important in many applications like ranking or scoring systems.
Program 4: Tree Sort for negative numbers
By default, Tree Sort works with any numeric value. This example shows sorting an array containing negative numbers.
use strict;
use warnings;
# ----------------------
# Node package (BST node)
# ----------------------
package Node;
# Constructor: create a new node
sub new {
my ($class, $value) = @_;
return bless { value => $value, left => undef, right => undef }, $class;
}
# Insert value into BST
sub insert {
my ($node, $value) = @_;
return Node->new($value) unless $node;
if ($value < $node->{value}) {
$node->{left} = insert($node->{left}, $value);
} else {
$node->{right} = insert($node->{right}, $value);
}
return $node;
}
# In-order traversal to get sorted array
sub inorder {
my ($node, $arr) = @_;
return unless $node;
inorder($node->{left}, $arr);
push @$arr, $node->{value};
inorder($node->{right}, $arr);
}
# ----------------------
# Main program
# ----------------------
package main;
my @arr = (-10, 20, -5, 15, 0, -2);
# Build BST
my $root;
$root = Node::insert($root, $_) for @arr;
# Traverse BST in-order to get sorted array
my @sorted;
Node::inorder($root, \@sorted);
# Print result
print "Sorted array: @sorted\n";Tree Sort handles negative numbers naturally because the comparison logic works for all numeric values. Beginners can experiment with positive, negative, and zero values in the same array.
Program 5: Tree Sort for floating-point numbers
Tree Sort can also sort floating-point numbers without extra adjustments. This program demonstrates sorting decimals in Perl.
use strict;
use warnings;
# ----------------------
# Node package (BST node)
# ----------------------
package Node;
# Constructor: create a new node
sub new {
my ($class, $value) = @_;
return bless { value => $value, left => undef, right => undef }, $class;
}
# Insert a value into BST
sub insert {
my ($node, $value) = @_;
return Node->new($value) unless $node;
if ($value < $node->{value}) {
$node->{left} = insert($node->{left}, $value);
} else {
$node->{right} = insert($node->{right}, $value);
}
return $node;
}
# In-order traversal: left, root, right
# Collects sorted values into array
sub inorder {
my ($node, $arr) = @_;
return unless $node;
inorder($node->{left}, $arr);
push @$arr, $node->{value};
inorder($node->{right}, $arr);
}
# ----------------------
# Main program
# ----------------------
package main;
# Array of decimal numbers (including negatives)
my @arr = (2.5, -1.2, 3.0, 0.5, -3.7);
# Build BST
my $root;
$root = Node::insert($root, $_) for @arr;
# Traverse BST to get sorted array
my @sorted;
Node::inorder($root, \@sorted);
# Print the sorted array
print "Sorted array: @sorted\n";This program shows that Tree Sort works seamlessly with decimal numbers. Beginners can see that floating-point values are handled naturally in the BST comparisons.
Frequently Asked Questions (FAQ)
This section answers common beginner questions about Tree Sort in Perl.
Q1. How does Tree Sort differ from other sorting algorithms?
Tree Sort uses a binary search tree to organize elements. Sorting happens automatically when performing an in-order traversal, unlike comparison-based algorithms that repeatedly swap elements.
Q2. Is Tree Sort fast?
Tree Sort is fast when the tree is balanced, offering O(n log n) performance. However, if the tree becomes unbalanced, it can degrade to O(n²).
Q3. Can Tree Sort handle duplicates?
Yes, duplicates are usually inserted in a consistent manner, either left or right, maintaining stability if handled properly.
Q4. Can Tree Sort work with negative and floating-point numbers?
Yes, Tree Sort naturally handles negative numbers and floating-point values as long as comparisons are done correctly.
Q5. When should I use Tree Sort?
Tree Sort is useful when you need both sorting and fast lookups, or when learning about trees and how data structures can be applied in algorithms.
Conclusion
Tree Sort is a practical and educational algorithm that combines sorting with the power of binary search trees. By building a BST and traversing it in order, you can efficiently sort integers, negative numbers, and floating-point numbers in Perl. The programs in this article show different ways to implement Tree Sort, from basic insertion and traversal to handling duplicates and various numeric types.
Beginners can learn a lot by experimenting with these examples, adding values, or trying different data structures. With practice, Tree Sort becomes an excellent tool for understanding both sorting and trees, forming a strong foundation for more advanced programming challenges.
