Sorting is one of the most important concepts in computer science and programming. It helps organize data so it becomes easier to access, process, and understand. There are many sorting algorithms out there — from simple ones like Bubble Sort and Insertion Sort to more advanced ones like Merge Sort and Quick Sort. Among these, Tree Sort stands out for its elegant use of a data structure known as a Binary Search Tree (BST).
with hands-on learning.
get the skills and confidence to land your next move.
Tree Sort works by first inserting all elements of the array into a binary search tree. The property of a BST is that the left child of a node contains smaller values, while the right child contains larger values. Once all elements are inserted, an in-order traversal (visiting the left node, then the root, then the right node) produces a sorted sequence. This makes Tree Sort both an educational and powerful example of how data structures and algorithms work together.
The algorithm is useful in cases where you want to maintain sorted order dynamically, as you can insert new data into the tree at any time and still retrieve the sorted data easily. It’s a great way for GoLang beginners to understand both sorting and trees in a single program.
Program 1: Basic Tree Sort Using Recursion
This first program shows the basic version of Tree Sort using a recursive approach. It creates a binary search tree, inserts all elements, and then performs an in-order traversal to produce the sorted result.
package main
import "fmt"
type Node struct {
value int
left *Node
right *Node
}
func insert(root *Node, value int) *Node {
if root == nil {
return &Node{value: value}
}
if value < root.value {
root.left = insert(root.left, value)
} else {
root.right = insert(root.right, value)
}
return root
}
func inorder(root *Node, result *[]int) {
if root != nil {
inorder(root.left, result)
*result = append(*result, root.value)
inorder(root.right, result)
}
}
func treeSort(arr []int) []int {
var root *Node
for _, value := range arr {
root = insert(root, value)
}
var result []int
inorder(root, &result)
return result
}
func main() {
arr := []int{5, 2, 8, 1, 9, 3}
fmt.Println("Original array:", arr)
sorted := treeSort(arr)
fmt.Println("Sorted array:", sorted)
}This program builds a binary search tree by inserting each element one by one. The recursive insert() function ensures that all smaller values go to the left subtree, and larger ones go to the right. Once the tree is built, an in-order traversal of the tree collects the elements in sorted order. This program helps beginners visualize how recursion and tree structures work hand in hand.
Program 2: Iterative Tree Sort (Without Recursion)
While recursion is easy to understand, it can sometimes be replaced with iteration. This next version uses an iterative approach to perform the in-order traversal, helping you understand another way of handling tree traversal.
package main
import "fmt"
type Node struct {
value int
left *Node
right *Node
}
func insertIter(root **Node, value int) {
if *root == nil {
*root = &Node{value: value}
return
}
current := *root
for {
if value < current.value {
if current.left == nil {
current.left = &Node{value: value}
break
}
current = current.left
} else {
if current.right == nil {
current.right = &Node{value: value}
break
}
current = current.right
}
}
}
func inorderIter(root *Node) []int {
stack := []*Node{}
result := []int{}
current := root
for current != nil || len(stack) > 0 {
for current != nil {
stack = append(stack, current)
current = current.left
}
current = stack[len(stack)-1]
stack = stack[:len(stack)-1]
result = append(result, current.value)
current = current.right
}
return result
}
func treeSortIterative(arr []int) []int {
var root *Node
for _, value := range arr {
insertIter(&root, value)
}
return inorderIter(root)
}
func main() {
arr := []int{7, 3, 9, 1, 6, 8, 10}
fmt.Println("Original array:", arr)
sorted := treeSortIterative(arr)
fmt.Println("Sorted array (Iterative):", sorted)
}In this version, both insertion and traversal are done iteratively. It avoids recursion by using loops and a stack to perform in-order traversal. Beginners can benefit from this by learning how stack-based iteration can mimic recursive behavior in tree operations.
Program 3: Tree Sort in Descending Order
Tree Sort can easily be modified to produce descending order output. This program simply reverses the traversal order to visit right nodes before left nodes.
package main
import "fmt"
type Node struct {
value int
left *Node
right *Node
}
func insert(root *Node, value int) *Node {
if root == nil {
return &Node{value: value}
}
if value < root.value {
root.left = insert(root.left, value)
} else {
root.right = insert(root.right, value)
}
return root
}
func reverseInorder(root *Node, result *[]int) {
if root != nil {
reverseInorder(root.right, result)
*result = append(*result, root.value)
reverseInorder(root.left, result)
}
}
func treeSortDesc(arr []int) []int {
var root *Node
for _, value := range arr {
root = insert(root, value)
}
var result []int
reverseInorder(root, &result)
return result
}
func main() {
arr := []int{5, 2, 8, 1, 9, 3}
fmt.Println("Original array:", arr)
sorted := treeSortDesc(arr)
fmt.Println("Sorted array (Descending):", sorted)
}Here, instead of visiting the left subtree first, the traversal visits the right one. This simple change produces the array in descending order. It’s a great way to see how traversal direction directly affects the final order of sorted data.
Program 4: Tree Sort With Strings
Tree Sort is not limited to numbers — it can also be used with strings or other data types. This example shows how to sort strings alphabetically using Tree Sort.
package main
import "fmt"
type Node struct {
value string
left *Node
right *Node
}
func insertString(root *Node, value string) *Node {
if root == nil {
return &Node{value: value}
}
if value < root.value {
root.left = insertString(root.left, value)
} else {
root.right = insertString(root.right, value)
}
return root
}
func inorderString(root *Node, result *[]string) {
if root != nil {
inorderString(root.left, result)
*result = append(*result, root.value)
inorderString(root.right, result)
}
}
func treeSortStrings(arr []string) []string {
var root *Node
for _, value := range arr {
root = insertString(root, value)
}
var result []string
inorderString(root, &result)
return result
}
func main() {
names := []string{"Hermione", "Ron", "Harry", "Draco", "Luna"}
fmt.Println("Original names:", names)
sorted := treeSortStrings(names)
fmt.Println("Sorted names:", sorted)
}This example replaces integers with strings. The tree is built based on lexicographical comparison, meaning words are sorted in alphabetical order. It’s a nice illustration of how the same algorithm can work with different data types when implemented correctly.
Frequently Asked Questions (FAQ)
Here are some common questions beginners often ask about Tree Sort in GoLang.
Q1: What is Tree Sort?
Tree Sort is a sorting algorithm that uses a binary search tree to arrange elements in order. It first inserts all items into the tree and then performs an in-order traversal to extract them in sorted order.
Q2: What is the time complexity of Tree Sort?
On average, Tree Sort runs in O(n log n) time, but in the worst case (when the tree becomes unbalanced), it can degrade to O(n²).
Q3: Why use Tree Sort instead of Quick Sort or Merge Sort?
Tree Sort helps visualize how trees work. It’s often used for teaching purposes or when you want to maintain a sorted structure dynamically.
Q4: Can Tree Sort handle duplicate elements?
Yes, duplicates can be stored by allowing equal values to go to either the left or right subtree.
Q5: Is Tree Sort stable?
By default, Tree Sort is not stable, because the relative order of equal elements can change depending on how they are inserted.
Conclusion
Tree Sort is a beautiful example of how data structures and algorithms complement each other. By using a binary search tree, it sorts data naturally through structure rather than repeated comparisons. It’s an excellent algorithm for beginners learning both sorting and trees in GoLang, as it teaches recursion, iteration, and traversal patterns in a simple yet powerful way.
By experimenting with the versions above — from recursive to iterative, ascending to descending, and numbers to strings — you’ll gain a deeper understanding of how flexible and logical Tree Sort can be. Keep practicing, tweak the code, and watch how data flows through the tree. Before long, you’ll not only understand sorting but also the foundation of how many data structures work behind the scenes.
