Hubbry Logo
Tree sortTree sortMain
Open search
Tree sort
Community hub
Tree sort
logo
8 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Tree sort
Tree sort
Tree sort
View on Wikipedia
from Wikipedia
Tree sort
ClassSorting algorithm
Data structureArray
Worst-case performanceO(n²) (unbalanced) O(n log n) (balanced)
Best-case performanceO(n log n) [citation needed]
Average performanceO(n log n)
Worst-case space complexityΘ(n)
OptimalYes, if balanced

A tree sort is a sort algorithm that builds a binary search tree from the elements to be sorted, and then traverses the tree (in-order) so that the elements come out in sorted order.[1] Its typical use is sorting elements online: after each insertion, the set of elements seen so far is available in sorted order.

Tree sort can be used as a one-time sort, but it is equivalent to quicksort as both recursively partition the elements based on a pivot, and since quicksort is in-place and has lower overhead, tree sort has few advantages over quicksort. It has better worst case complexity when a self-balancing tree is used, but even more overhead.

Efficiency

[edit]

Adding one item to a binary search tree is on average an O(log n) process (in big O notation). Adding n items is an O(n log n) process, making tree sorting a 'fast sort' process. Adding an item to an unbalanced binary tree requires O(n) time in the worst-case: When the tree resembles a linked list (degenerate tree). This results in a worst case of O(n²) time for this sorting algorithm. This worst case occurs when the algorithm operates on an already sorted set, or one that is nearly sorted, reversed or nearly reversed. Expected O(n log n) time can however be achieved by shuffling the array, but this does not help for equal items.

The worst-case behaviour can be improved by using a self-balancing binary search tree. Using such a tree, the algorithm has an O(n log n) worst-case performance, thus being degree-optimal for a comparison sort. However, tree sort algorithms require separate memory to be allocated for the tree, as opposed to in-place algorithms such as quicksort or heapsort. On most common platforms, this means that heap memory has to be used, which is a significant performance hit when compared to quicksort and heapsort[citation needed]. When using a splay tree as the binary search tree, the resulting algorithm (called splaysort) has the additional property that it is an adaptive sort, meaning that its running time is faster than O(n log n) for inputs that are nearly sorted.

Example

[edit]

The following tree sort algorithm in pseudocode accepts a collection of comparable items and outputs the items in ascending order: 

 STRUCTURE BinaryTree
     BinaryTree:LeftSubTree
     Object:Node
     BinaryTree:RightSubTree
 
 PROCEDURE Insert(BinaryTree:searchTree, Object:item)
     IF searchTree.Node IS NULL THEN
         SET searchTree.Node TO item
     ELSE
         IF item IS LESS THAN searchTree.Node THEN
             Insert(searchTree.LeftSubTree, item)
         ELSE
             Insert(searchTree.RightSubTree, item)
 
 PROCEDURE InOrder(BinaryTree:searchTree)
     IF searchTree.Node IS NULL THEN
         EXIT PROCEDURE
     ELSE
         InOrder(searchTree.LeftSubTree)
         EMIT searchTree.Node
         InOrder(searchTree.RightSubTree)
 
 PROCEDURE TreeSort(Collection:items)
     BinaryTree:searchTree
    
     FOR EACH individualItem IN items
         Insert(searchTree, individualItem)
    
     InOrder(searchTree)

In a simple functional programming form, the algorithm (in Haskell) would look something like this: 

 data Tree a = Leaf | Node (Tree a) a (Tree a)

 insert :: Ord a => a -> Tree a -> Tree a
 insert x Leaf = Node Leaf x Leaf
 insert x (Node t y s)
     | x <= y = Node (insert x t) y s
     | x > y  = Node t y (insert x s)

 flatten :: Tree a -> [a]
 flatten Leaf = []
 flatten (Node t x s) = flatten t ++ [x] ++ flatten s

 treesort :: Ord a => [a] -> [a]
 treesort = flatten . foldr insert Leaf

In the above implementation, both the insertion algorithm and the retrieval algorithm have O(n²) worst-case scenarios.

[edit]

References

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Tree sort

View on Grokipedia
from Grokipedia
Tree sort is a comparison-based sorting algorithm that builds a binary search tree from the input elements and then retrieves them in sorted order via an in-order traversal of the tree. The process begins by inserting each element into the binary search tree, where the tree's structure ensures that left subtrees contain smaller values and right subtrees contain larger ones, maintaining the search tree property. Once all elements are inserted, an in-order traversal visits nodes in ascending order, effectively producing the sorted list without additional comparisons. This algorithm is a variant of insertion sort, as each insertion mimics the insertion step but leverages the tree for efficient placement. In terms of time complexity, tree sort achieves an average-case performance of O(n log n) when the tree remains balanced, but it can degrade to O(n²) in the worst case if the input causes a degenerate (unbalanced) tree, similar to a linked list. It is stable, preserving the relative order of equal elements, and requires O(n) extra space for the tree structure. Using self-balancing variants like AVL or red-black trees can guarantee the optimal O(n log n) bound.

Overview

Definition

Tree sort is a comparison-based that utilizes a (BST) to organize and retrieve elements in sorted order. It operates by first constructing a BST from the input elements, leveraging the tree's inherent ordering properties to facilitate efficient arrangement without requiring explicit comparisons during the final output phase. The core concept involves inserting each element from the unsorted list into the BST, where the tree maintains the invariant that all values in a node's left subtree are less than the node's value, and all values in the right subtree are greater. A is a specialized that supports this ordering, enabling logarithmic-time insertions on average for balanced trees. Subsequent in-order traversal of the BST—recursively processing the left subtree, the node itself, and then the right subtree—produces the elements in ascending sorted sequence. This hybrid method combines tree insertion for dynamic organization with traversal for extraction, distinguishing it from purely array-based sorters. Tree sort offers an alternative to algorithms like or , proving beneficial in scenarios where tree structures excel, such as online sorting of incrementally arriving data or maintaining stability for equal elements.

History

Tree sort originated in the early alongside the development of binary search trees (BSTs), which provide the foundational for the algorithm. The BST was independently invented in 1960 by researchers P. F. Windley, A. D. Booth, A. J. T. Colin, and T. N. Hibbard as an efficient method for storing and searching ordered data. This structure enabled the conceptualization of sorting via tree insertion followed by in-order traversal, emerging amid broader research into tree-based algorithms during that decade. A key milestone came with the formal analysis and description of tree-based sorting in influential algorithm literature. Donald Knuth's 1973 book The Art of Computer Programming, Volume 3: Sorting and Searching discusses tree structures and their applications in sorting (Chapter 5) and searching (Chapter 6), including methods that leverage binary trees for ordered data processing and highlighting their properties for producing sorted output. Knuth's work, drawing on prior BST developments, solidified the place of such tree-based approaches in algorithmic theory. In the ensuing decades, tree sort evolved primarily as an educational tool rather than a practical implementation. By the 1980s, variations incorporating balanced BSTs, such as AVL trees invented in 1962, were explored to address structural imbalances, though these adaptations remained niche. As of 2025, tree sort continues to serve mainly pedagogical purposes, illustrating BST operations and traversal techniques in curricula, with limited adoption in production systems due to more efficient alternatives.

Algorithm

Binary Search Tree Basics

A (BST) is a type of where each node contains a key, and for any given node, all keys in its left subtree are less than the node's key, while all keys in its right subtree are greater than or equal to the node's key. This ordering property is maintained recursively across all nodes, ensuring that the tree structure supports efficient searching and organization of data. BSTs can permit duplicate keys by directing equal keys to the right subtree, allowing multiple nodes with the same value while preserving the search properties. The efficiency of a BST is largely determined by its , which is the longest path from the to a leaf node. In a balanced BST, the is approximately logarithmic in the number of nodes, enabling fast operations; however, if insertions occur in a sorted or nearly sorted order, the tree can become unbalanced, resembling a and leading to linear performance degradation. This height dependency underscores the importance of the 's shape in practical applications, where maintaining balance is often crucial for consistent performance. Basic operations in a BST, including search, insertion, and deletion, operate by traversing from the downward, leveraging the ordering to prune unnecessary branches. Each of these operations takes time proportional to the h of the , yielding an average-case complexity of O(log n) for balanced trees but potentially O(n) in the worst case for unbalanced ones. To address the risks of imbalance, self-balancing variants of BSTs, such as AVL trees introduced by Adelson-Velsky and Landis in 1962 and red-black trees developed by in 1972, incorporate rotation and coloring mechanisms to keep the height bounded by O(log n). These enhancements ensure logarithmic performance without delving into the specific balancing algorithms here.

Insertion and In-order Traversal Steps

Tree sort operates in two primary phases: constructing a (BST) from the input elements and then extracting the sorted sequence through traversal. The process begins by initializing an empty BST. Each element from the unsorted input array is inserted sequentially, starting from the first element. During insertion, if the tree is empty, the element becomes the root node. Otherwise, the insertion algorithm compares the new element's key with the current node's key: if smaller, it recurses to the left subtree; otherwise (equal or larger), it recurses to the right subtree. This continues until a null position is found, where the new node is attached as a leaf. Once all elements are inserted, the BST maintains the property that in-order traversal will visit nodes in ascending order. The second phase performs an in-order traversal, which recursively visits the left subtree, processes the current node (by adding its value to an output ), and then visits the right subtree. This traversal collects the elements into a sorted or , yielding the final sorted output. The resulting contains the elements in non-decreasing order, assuming the BST properties hold. In this implementation, equal keys are directed to the right subtree, allowing duplicates to be included and preserving their relative order from the input to ensure stability. The following high-level illustrates the insertion and traversal steps:

function treeSort(inputArray): root = null for each element in inputArray: root = insert(root, element) sortedArray = [] inOrderTraversal(root, sortedArray) return sortedArray function insert(node, key): if node is null: return new Node(key) if key < node.key: node.left = insert(node.left, key) else: node.right = insert(node.right, key) return node function inOrderTraversal(node, sortedArray): if node is not null: inOrderTraversal(node.left, sortedArray) append node.key to sortedArray inOrderTraversal(node.right, sortedArray)

function treeSort(inputArray): root = null for each element in inputArray: root = insert(root, element) sortedArray = [] inOrderTraversal(root, sortedArray) return sortedArray function insert(node, key): if node is null: return new Node(key) if key < node.key: node.left = insert(node.left, key) else: node.right = insert(node.right, key) return node function inOrderTraversal(node, sortedArray): if node is not null: inOrderTraversal(node.left, sortedArray) append node.key to sortedArray inOrderTraversal(node.right, sortedArray)

After traversal, the original tree structure is typically discarded, as the sorted output is stored separately; the process is not in-place unless the input array is overwritten during traversal.

Analysis

Time Complexity

The time complexity of tree sort is primarily determined by the cost of inserting elements into the binary search tree (BST) followed by the in-order traversal to produce the sorted output. The traversal step requires O(n) time, as it visits each of the n nodes exactly once. Thus, the overall performance is dominated by the insertion phase, where each of the n elements is inserted sequentially into the BST. In the average case, assuming random input order that leads to a reasonably balanced tree, each insertion takes O(log n) time on average, resulting in a total time complexity of O(n log n) for the insertions plus O(n) for traversal, yielding O(n log n) overall. This average-case bound arises because the expected height of the tree remains O(log n) under random permutations, ensuring that the search path for each insertion averages logarithmic length. The worst-case time complexity occurs when the input is already sorted or reverse-sorted, causing the BST to degenerate into a linear chain with height O(n). In this scenario, each insertion after the first traverses nearly the entire existing tree, taking O(i) time for the i-th insertion, leading to a total insertion cost of O(n²) and overall O(n²) time complexity. The best case also achieves O(n log n), typically with inputs that maintain tree balance, such as random orders. More formally, the total time T(n) for insertions can be expressed as the sum of the heights traversed during each insertion:
T(n)=∑i=1nO(hi)+O(n),T(n) = \sum_{i=1}^{n} O(h_i) + O(n),
where hih_i is the height of the tree after i-1 insertions (i.e., the depth of the path to the insertion point for the i-th element), and the O(n) accounts for the traversal. In the balanced case, each hih_i is O(log i), so the sum evaluates to O(n log n); in the skewed case, hi≈ih_i \approx i, yielding O(n²). This derivation highlights how tree balance directly influences performance. A key factor affecting the time complexity is the order of input elements, as basic tree sort lacks any balancing mechanism like rotations (found in AVL or red-black trees), making it sensitive to pathological inputs that unbalance the structure.

Space Complexity

Tree sort requires O(n) space to store the binary search tree (BST) constructed from n elements, as each element is represented by a node containing the value and two pointers to child nodes. This storage is necessary regardless of the input order, since the tree holds all elements during the sorting process. In comparison to array-based sorts like insertion sort, tree sort incurs higher constant factors due to the additional pointers—typically two per node—beyond the element values themselves. The auxiliary space for recursive operations in tree sort, such as insertion into the BST and the subsequent in-order traversal, is O(h), where h is the height of the tree. In the average case for random inputs, the BST is balanced with h = O(log n), leading to O(log n) auxiliary space from the recursion stack. However, in the worst case of skewed inputs (e.g., already sorted data), h = O(n), resulting in O(n) auxiliary space. Tree sort is not truly in-place, as the tree structure demands additional memory proportional to n, separate from the input array. Even if the output sorted list is constructed in a new array during traversal, it requires another O(n) space; attempts to reuse the input array cannot eliminate the tree's overhead. The total space complexity can thus be expressed as: S(n)=O(n)+O(h)S(n) = O(n) + O(h) where the O(n) term dominates for the nodes and the O(h) accounts for the recursion stack.

Implementation and Examples

Pseudocode

The pseudocode for tree sort outlines a recursive implementation using a binary search tree (BST), where elements are inserted to form the tree and then extracted in sorted order via in-order traversal, producing a new list containing all input elements. To ensure stability (preserving the relative order of equal elements), duplicates are inserted into the right subtree. The node structure for the BST is defined as follows:

structure Node value: element left: Node or null right: Node or null end structure

structure Node value: element left: Node or null right: Node or null end structure

The insertion function recursively builds the BST by placing each value in the appropriate subtree based on comparisons. Duplicates (value == current.value) are treated as greater or equal and inserted to the right to maintain stability.

procedure insert(current: Node, value: element) returns Node if current is null return new Node with value, left=null, right=null if value < current.value current.left = insert(current.left, value) else current.right = insert(current.right, value) return current end procedure

procedure insert(current: Node, value: element) returns Node if current is null return new Node with value, left=null, right=null if value < current.value current.left = insert(current.left, value) else current.right = insert(current.right, value) return current end procedure

The in-order traversal function recursively visits nodes to append values to a result list in ascending order: left subtree, current node, right subtree.

procedure inOrder(current: Node, result: list) if current is null return inOrder(current.left, result) append current.value to result inOrder(current.right, result) end procedure

procedure inOrder(current: Node, result: list) if current is null return inOrder(current.left, result) append current.value to result inOrder(current.right, result) end procedure

The main tree sort procedure initializes an empty tree, inserts all input elements, performs the in-order traversal to populate a new sorted list, and returns it. This pseudocode assumes no null or invalid inputs for simplicity. Iterative alternatives for insertion and traversal exist to mitigate stack overflow risks in deeply unbalanced trees.

function treeSort(input: array of elements) returns array root = null for each value in input root = insert(root, value) sorted = empty list inOrder(root, sorted) return sorted end function

function treeSort(input: array of elements) returns array root = null for each value in input root = insert(root, value) sorted = empty list inOrder(root, sorted) return sorted end function

Worked Example

To illustrate the tree sort process, consider the unsorted array [5, 3, 8, 4, 2]. The algorithm begins by constructing a binary search tree (BST) through sequential insertion of each element, following standard BST rules where each new node is placed to the left if smaller than the parent or to the right if larger or equal, recursing until the appropriate leaf position is found. Start with an empty tree and insert 5, which becomes the root node. Next, insert 3, which is less than 5 and thus becomes the left child of 5. Insert 8, which is greater than 5 and becomes the right child of 5. Then, insert 4, which is greater than 3 (the left child of 5) but less than 5, so it becomes the right child of 3. Finally, insert 2, which is less than 3 and thus becomes the left child of 3. The resulting BST structure is:

5 / \ 3 8 / \ 2 4

5 / \ 3 8 / \ 2 4

To obtain the sorted array, perform an in-order traversal of the tree, which visits nodes in the order: left subtree, root, right subtree. This yields: 2 (left of 3), 3 (root of left subtree), 4 (right of 3), 5 (root), 8 (right of 5), producing the sorted array [2, 3, 4, 5, 8]. As an edge case, consider the already-sorted input [1, 2, 3, 4, 5]. Sequential insertion into a BST results in a right-skewed tree forming a linear chain (1 as root, 2 as right child of 1, 3 as right child of 2, and so on), which demonstrates how tree sort can degrade to quadratic performance in the worst case due to unbalanced structure. To demonstrate handling of duplicates and stability, consider the input [5, 3, 5, 4]. Insert 5 (root), 3 (left of 5), second 5 (>=5, right of 5), 4 (>3, <5, right of 3). The tree is:

5 / \ 3 5 \ 4

5 / \ 3 5 \ 4

In-order traversal: 3, 4, 5 (first), 5 (second), preserving the order of the two 5s as in the input. Sorted: [3, 4, 5, 5].

Comparisons and Applications

Comparison to Other Algorithms

Tree sort shares similarities with in its average-case of O(n log n), achieved through dynamic partitioning of data during insertions into the , but employs a more efficient pivot-based partitioning that reduces constant factors and performs better in practice for large datasets. However, both algorithms risk a worst-case O(n²) performance— from poor pivot choices and tree sort from skewed tree structures—though 's randomized variants mitigate this more reliably. Tree sort is , preserving the relative order of equal elements when duplicates are handled by inserting to the right subtree, whereas is typically unstable unless modified with additional space. In comparison to , tree sort evokes a divide-and-conquer by incrementally building a sorted structure through insertions, but it relies on tree height for efficiency rather than merge sort's fixed logarithmic depth, leading to less predictable performance. guarantees O(n log n) time in all cases and maintains stability by preserving the order of equal elements during merging, making it preferable for applications requiring consistent behavior, such as of large files, while tree sort's potential for imbalance introduces variability. Both tree sort and heap sort leverage tree structures for organization, with tree sort using a binary search tree for insertions and in-order traversal, contrasted by heap sort's use of a complete binary heap for selection-based extraction. Heap sort operates in-place with a guaranteed O(n log n) time complexity across all cases and minimal auxiliary space, offering reliable performance without the degeneration risk inherent to tree sort's O(n²) worst case from unbalanced trees. Tree sort stands out for its integration of search and sorting operations within the same binary search tree framework, which proves advantageous in database indexing contexts where maintaining sorted access to data facilitates efficient queries alongside ordering.
AlgorithmAverage Time ComplexityWorst-Case Time ComplexityStability
QuicksortO(n log n)O(n²)No
Merge sortO(n log n)O(n log n)Yes
Heap sortO(n log n)O(n log n)No
Tree sortO(n log n)O(n²)Yes

Advantages and Disadvantages

Tree sort provides an intuitive approach for learning binary search trees, as it leverages fundamental BST operations like insertion and in-order traversal to produce a sorted sequence, making it a valuable educational tool in curricula. This method also enables partial sorting, where subsets of the data can be traversed and extracted in order without rebuilding the entire tree. Additionally, it integrates seamlessly with tree-based data structures in storage systems, allowing sorted output directly from the tree without separate sorting steps. Recent variants, such as TSort, optimize tree sort for hybrid DRAM-persistent memory systems, improving bandwidth and reducing writes in modern byte-addressable storage scenarios as of 2024. In practical scenarios, tree sort excels as a aid and finds niche use in dynamic datasets where elements arrive incrementally, supporting online sorting without requiring all data upfront. Despite these strengths, tree sort has notable limitations that restrict its broader adoption. The algorithm is highly sensitive to input order, potentially degrading to O(n²) performance in the worst case when the tree becomes unbalanced, such as with already sorted or reverse-sorted inputs. Moreover, it incurs higher constant factors due to pointer manipulations and random memory accesses in tree construction and traversal, leading to poorer cache performance compared to array-based sorts. As of November 2025, tree sort is rarely implemented in sorting functions; for instance, Python's sorted() employs Powersort, an adaptive based on and , optimized for real-world data (introduced in Python 3.11). Similarly, Java's Arrays.sort() uses for object arrays and a dual-pivot variant for primitives, prioritizing stability and over tree-based approaches. To address key drawbacks, tree sort can be improved by employing self-balancing BST variants like AVL trees or red-black trees, which ensure logarithmic height and consistent O(n log n) worst-case performance regardless of input order.

References

  1. https://cs.lmu.edu/~ray/notes/sorting/
  2. https://www.cs.uah.edu/~mdb0013/Sorting/TreeSort.html
  3. https://web.cs.unlv.edu/larmore/Courses/CSC477/F22/Handouts/sorting.pdf
  4. https://www.baeldung.com/cs/sorting-binary-tree
  5. https://xlinux.nist.gov/dads/HTML/treesort1.html
  6. https://www.educative.io/blog/what-is-tree-sort
  7. http://mplab.sztaki.hu/~nbalazs/alg_web/bs.html
  8. https://www-cs-faculty.stanford.edu/~knuth/taocp.html
  9. https://www.cs.cornell.edu/courses/JavaAndDS/files/tree5BSTextensions.pdf
  10. https://www.geeksforgeeks.org/dsa/tree-sort/
  11. https://opendsa-server.cs.vt.edu/ODSA/Books/Everything/html/BST.html
  12. https://courses.grainger.illinois.edu/cs225/fa2021/resources/bst/
  13. https://www.geeksforgeeks.org/dsa/how-to-handle-duplicates-in-binary-search-tree/
  14. https://web.stanford.edu/class/archive/cs/cs161/cs161.1168/lecture8.pdf
  15. https://pages.cs.wisc.edu/~siff/CS367/Notes/bsts.html
  16. https://cs.nyu.edu/algvis/java/bst.html
  17. https://softwarefoundations.cis.upenn.edu/vfa-current/SearchTree.html
  18. https://www.cs.princeton.edu/courses/archive/fall09/cos521/Handouts/WADSrb-trees.pdf
  19. https://faculty.cs.niu.edu/~winans/notes/Data_Structures/binary_search_trees.html
  20. https://www.cs.cmu.edu/~clo/www/CMU/DataStructures/Lessons/lesson4_3.htm
  21. https://rosettacode.org/wiki/Sorting_algorithms/Tree_sort_on_a_linked_list
  22. https://cs.lmu.edu/~ray/notes/binarysearchtrees/
  23. https://algorithm-wiki.csail.mit.edu/wiki/Tree_sort_(Comparison_Sorting_Sorting)
  24. https://web.cs.unlv.edu/larmore/Courses/CSC477/S25/Handouts/sorting.pdf
  25. https://www.geeksforgeeks.org/dsa/complexity-different-operations-binary-tree-binary-search-tree-avl-tree/
  26. https://www.sarthaks.com/2388556/binary-tree-sort-is-an-in-place-sorting-algorithm
  27. https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/resources/lecture-5-binary-search-trees-bst-sort/
  28. https://www.cs.rochester.edu/u/gildea/csc282/slides/C12-bst.pdf
  29. https://www.geeksforgeeks.org/tree-sort/
  30. https://engineering.purdue.edu/ece264/21sp/hw/HW13
  31. https://condor.depaul.edu/ichu/csc383/notes/notes2/sorting.pdf
  32. https://web.cs.unlv.edu/larmore/Courses/CSC477/S22/Handouts/sorting.pdf
  33. https://www.geeksforgeeks.org/dsa/binary-search-tree-data-structure/
  34. https://www.vldb.org/pvldb/vol17/p1487-zheng.pdf
  35. https://news.liverpool.ac.uk/2022/12/12/liverpool-computer-scientists-improve-python-sorting-function/
  36. https://www.baeldung.com/java-sorting
Add your contribution
Related Hubs
User Avatar
No comments yet.