Sorting is one of the most common tasks in programming, and there are many algorithms available to help you organize data efficiently. One such algorithm is Tree Sort, which is based on the Binary Search Tree (BST) data structure. In Tree Sort, we first insert all the elements of the array into a BST, and then perform an in-order traversal to retrieve the elements in sorted order. This method guarantees that the output is always sorted, and it can handle both positive and negative numbers.
with hands-on learning.
get the skills and confidence to land your next move.
Tree Sort is particularly useful when you need a dynamic sorted structure because the BST allows for efficient insertion and search operations. Unlike simpler algorithms such as Bubble Sort or Selection Sort, Tree Sort uses a tree structure, which helps beginners understand data organization and traversal concepts in addition to sorting. It’s widely used in applications where you need sorted data with quick insertions, like in databases or real-time systems.
Program 1: Basic Tree Sort Using Recursion
This program demonstrates a simple recursive implementation of Tree Sort. It inserts each element into a binary search tree and then performs an in-order traversal to sort the data.
Module Module1
Class Node
Public Value As Integer
Public Left As Node
Public Right As Node
Public Sub New(val As Integer)
Value = val
Left = Nothing
Right = Nothing
End Sub
End Class
Function Insert(root As Node, val As Integer) As Node
If root Is Nothing Then
Return New Node(val)
End If
If val < root.Value Then
root.Left = Insert(root.Left, val)
Else
root.Right = Insert(root.Right, val)
End If
Return root
End Function
Sub InOrder(root As Node, ByRef result As List(Of Integer))
If root IsNot Nothing Then
InOrder(root.Left, result)
result.Add(root.Value)
InOrder(root.Right, result)
End If
End Sub
Sub Main()
Dim data() As Integer = {5, 3, 7, 1, 4, 6, 2}
Dim root As Node = Nothing
For Each num In data
root = Insert(root, num)
Next
Dim sorted As New List(Of Integer)
InOrder(root, sorted)
Console.WriteLine("Sorted Array:")
For Each num In sorted
Console.Write(num & " ")
Next
Console.ReadLine()
End Sub
End ModuleThe program uses a Node class to build a BST. Each value is inserted based on comparison with the current node. The in-order traversal collects the elements in sorted order. This approach helps beginners understand recursion and tree traversal while performing sorting efficiently.
Program 2: Tree Sort with Duplicate Handling
Sometimes arrays contain duplicate numbers. This program shows how to handle duplicates by allowing multiple nodes with the same value in the BST.
Module Module1
Class Node
Public Value As Integer
Public Left As Node
Public Right As Node
Public Sub New(val As Integer)
Value = val
Left = Nothing
Right = Nothing
End Sub
End Class
Function Insert(root As Node, val As Integer) As Node
If root Is Nothing Then
Return New Node(val)
End If
If val <= root.Value Then
root.Left = Insert(root.Left, val)
Else
root.Right = Insert(root.Right, val)
End If
Return root
End Function
Sub InOrder(root As Node, ByRef result As List(Of Integer))
If root IsNot Nothing Then
InOrder(root.Left, result)
result.Add(root.Value)
InOrder(root.Right, result)
End If
End Sub
Sub Main()
Dim data() As Integer = {5, 3, 7, 1, 4, 6, 2}
Dim root As Node = Nothing
For Each num In data
root = Insert(root, num)
Next
Dim sorted As New List(Of Integer)
InOrder(root, sorted)
Console.WriteLine("Sorted Array:")
For Each num In sorted
Console.Write(num & " ")
Next
Console.ReadLine()
End Sub
End ModuleBy inserting duplicates into the left subtree, we preserve the order of elements and avoid overwriting. This is useful when you want to maintain stability in the sorting process.
Program 3: Iterative Insertion in Tree Sort
This version avoids recursion during insertion, using a loop to place elements in the tree.
Module Module1
Class Node
Public Value As Integer
Public Left As Node
Public Right As Node
Public Sub New(val As Integer)
Value = val
Left = Nothing
Right = Nothing
End Sub
End Class
Function InsertIterative(root As Node, val As Integer) As Node
Dim newNode As New Node(val)
If root Is Nothing Then Return newNode
Dim current As Node = root
Dim parent As Node = Nothing
While current IsNot Nothing
parent = current
If val < current.Value Then
current = current.Left
Else
current = current.Right
End If
End While
If val < parent.Value Then
parent.Left = newNode
Else
parent.Right = newNode
End If
Return root
End Function
Sub InOrder(root As Node, ByRef result As List(Of Integer))
If root IsNot Nothing Then
InOrder(root.Left, result)
result.Add(root.Value)
InOrder(root.Right, result)
End If
End Sub
Sub Main()
Dim data() As Integer = {5, 3, 7, 3, 1, 4, 6, 2}
Dim root As Node = Nothing
For Each num In data
root = InsertIterative(root, num)
Next
Dim sorted As New List(Of Integer)
InOrder(root, sorted)
Console.WriteLine("Sorted Array:")
For Each num In sorted
Console.Write(num & " ")
Next
Console.ReadLine()
End Sub
End ModuleThis approach is beginner-friendly for understanding loops vs recursion. It avoids stack overflow in large arrays and is more memory-efficient.
Program 4: Tree Sort for Negative and Positive Numbers
This program demonstrates that Tree Sort naturally handles both negative and positive numbers without any modification.
Module Module1
Class Node
Public Value As Integer
Public Left As Node
Public Right As Node
Public Sub New(val As Integer)
Value = val
Left = Nothing
Right = Nothing
End Sub
End Class
Function InsertIterative(root As Node, val As Integer) As Node
Dim newNode As New Node(val)
If root Is Nothing Then Return newNode
Dim current As Node = root
Dim parent As Node = Nothing
While current IsNot Nothing
parent = current
If val < current.Value Then
current = current.Left
Else
current = current.Right
End If
End While
If val < parent.Value Then
parent.Left = newNode
Else
parent.Right = newNode
End If
Return root
End Function
Sub InOrder(root As Node, ByRef result As List(Of Integer))
If root IsNot Nothing Then
InOrder(root.Left, result)
result.Add(root.Value)
InOrder(root.Right, result)
End If
End Sub
Sub Main()
Dim data() As Integer = {-10, 5, 0, -3, 8, -1}
Dim root As Node = Nothing
For Each num In data
root = InsertIterative(root, num)
Next
Dim sorted As New List(Of Integer)
InOrder(root, sorted)
Console.WriteLine("Sorted Array:")
For Each num In sorted
Console.Write(num & " ")
Next
Console.ReadLine()
End Sub
End ModuleSince BST comparisons work with any integer values, negative numbers are inserted into the left subtree and positive numbers into the right. Tree Sort is versatile and handles mixed arrays effectively.
Program 5: Tree Sort Using List for Output
Instead of printing directly, this version collects sorted elements in a List object. This makes it easier to return sorted data from functions or use it in other parts of the program.
Module Module1
Class Node
Public Value As Integer
Public Left As Node
Public Right As Node
Public Sub New(val As Integer)
Value = val
Left = Nothing
Right = Nothing
End Sub
End Class
Function InsertIterative(root As Node, val As Integer) As Node
Dim newNode As New Node(val)
If root Is Nothing Then Return newNode
Dim current As Node = root
Dim parent As Node = Nothing
While current IsNot Nothing
parent = current
If val < current.Value Then
current = current.Left
Else
current = current.Right
End If
End While
If val < parent.Value Then
parent.Left = newNode
Else
parent.Right = newNode
End If
Return root
End Function
Sub InOrder(root As Node, ByRef result As List(Of Integer))
If root IsNot Nothing Then
InOrder(root.Left, result)
result.Add(root.Value)
InOrder(root.Right, result)
End If
End Sub
Sub Main()
Dim data() As Integer = {-10, 5, 0, -3, 8, -1}
Dim root As Node = Nothing
For Each num In data
root = InsertIterative(root, num)
Next
Dim sorted As New List(Of Integer)
InOrder(root, sorted)
Console.WriteLine("Sorted Array:")
For Each num In sorted
Console.Write(num & " ")
Next
Console.ReadLine()
End Sub
End ModuleUsing a List improves flexibility for beginners who want to manipulate the sorted array, like filtering, mapping, or combining with other data structures.
Program 6: Tree Sort with User Input
This program lets the user input numbers at runtime to be sorted.
Module Module1
Class Node
Public Value As Integer
Public Left As Node
Public Right As Node
Public Sub New(val As Integer)
Value = val
Left = Nothing
Right = Nothing
End Sub
End Class
Function InsertIterative(root As Node, val As Integer) As Node
Dim newNode As New Node(val)
If root Is Nothing Then Return newNode
Dim current As Node = root
Dim parent As Node = Nothing
While current IsNot Nothing
parent = current
If val < current.Value Then
current = current.Left
Else
current = current.Right
End If
End While
If val < parent.Value Then
parent.Left = newNode
Else
parent.Right = newNode
End If
Return root
End Function
Sub InOrder(root As Node, ByRef result As List(Of Integer))
If root IsNot Nothing Then
InOrder(root.Left, result)
result.Add(root.Value)
InOrder(root.Right, result)
End If
End Sub
Sub Main()
Console.WriteLine("Enter numbers separated by space:")
Dim input As String = Console.ReadLine()
Dim data() As Integer = Array.ConvertAll(input.Split(" "c), Function(s) Int32.Parse(s))
Dim root As Node = Nothing
For Each num In data
root = InsertIterative(root, num)
Next
Dim sorted As New List(Of Integer)
InOrder(root, sorted)
Console.WriteLine("Sorted Array:")
For Each num In sorted
Console.Write(num & " ")
Next
Console.ReadLine()
End Sub
End ModuleIt introduces user input handling and array conversion in VB .NET. Beginners learn how to combine input/output with sorting logic.
Program 7: Tree Sort for Floating-Point Numbers
This version adapts Tree Sort to sort decimal numbers. Since BST comparisons work with Double, it naturally handles floating-point values.
Module Module1
Class NodeF
Public Value As Double
Public Left As NodeF
Public Right As NodeF
Public Sub New(val As Double)
Value = val
Left = Nothing
Right = Nothing
End Sub
End Class
Function InsertIterative(root As NodeF, val As Double) As NodeF
Dim newNode As New NodeF(val)
If root Is Nothing Then Return newNode
Dim current As NodeF = root
Dim parent As NodeF = Nothing
While current IsNot Nothing
parent = current
If val < current.Value Then
current = current.Left
Else
current = current.Right
End If
End While
If val < parent.Value Then
parent.Left = newNode
Else
parent.Right = newNode
End If
Return root
End Function
Sub InOrder(root As NodeF, ByRef result As List(Of Double))
If root IsNot Nothing Then
InOrder(root.Left, result)
result.Add(root.Value)
InOrder(root.Right, result)
End If
End Sub
Sub Main()
' Sample Double data
Dim data() As Double = {10.2, 3.5, 7.8, 1.1, 9.6, 4.4}
Dim root As NodeF = Nothing
For Each num As Double In data
root = InsertIterative(root, num)
Next
Dim sorted As New List(Of Double)
InOrder(root, sorted)
Console.WriteLine("Sorted Array:")
For Each num As Double In sorted
Console.Write(num & " ")
Next
Console.ReadLine()
End Sub
End ModuleThis demonstrates the versatility of Tree Sort. The same logic applies to integers, negatives, and decimals, making it a robust sorting algorithm for beginners to explore.
Frequently Asked Questions (FAQ)
Here are some common questions beginners ask about Tree Sort.
Q1: Can Tree Sort handle negative numbers?
Yes. The binary search tree structure allows negative numbers to be inserted in the left subtree naturally.
Q2: Is Tree Sort stable?
By default, Tree Sort is not stable, as it does not guarantee the original order of duplicate elements.
Q3: Can Tree Sort handle floating-point numbers?
Yes. You can use Double instead of Integer in the Node class to sort decimal numbers.
Q4: Is Tree Sort faster than Bubble Sort?
Tree Sort has an average time complexity of O(n log n), making it generally faster than Bubble Sort (O(n²)), especially for larger arrays.
Q5: Can I implement Tree Sort iteratively?
Yes. You can use a loop instead of recursion for insertion, which can reduce stack usage for very large datasets.
Conclusion
Tree Sort is a powerful and versatile sorting algorithm that introduces beginners to binary search trees, recursion, and traversal techniques. It works naturally with negative, positive, and floating-point numbers. By exploring different implementations—recursive, iterative, handling duplicates, and user input—you gain a solid foundation in both sorting algorithms and data structures. Practicing Tree Sort helps you understand how data can be organized efficiently, preparing you for more advanced programming challenges.
Tree Sort is not just about sorting—it’s about thinking in trees, a skill that is incredibly useful in computer science and real-world applications. Start experimenting with the examples above, modify them, and try combining Tree Sort with other algorithms to see how powerful these concepts can be.
