Summary

Tree Sort operates in two main phases. First, it iterates through the input array, inserting each element into a Binary Search Tree. A BST has the property that for any given node, all values in its left subtree are smaller, and all values in its right subtree are greater or equal. The second phase involves performing an in-order traversal of the BST (visiting the left subtree, then the node itself, then the right subtree), which naturally visits the nodes in ascending order. The values are then placed back into the original array, resulting in a sorted list.

How it Works

• 1. Initialize: Create an empty Binary Search Tree (BST).

• 2. Build Tree: Iterate through the input array from the first to the last element. For each element, insert it into the BST according to the rules: smaller values go left, larger or equal values go right.

• 3. In-order Traversal: Once all elements are inserted, perform a recursive in-order traversal starting from the root of the tree.

• 4. Overwrite Array: As each node is visited during the traversal, take its value and place it into the original array, starting from the first index. This overwrites the original unsorted array with the new sorted sequence.