Learn Computer Science
Developing a more interesting World
"Computer science is no more about computers than astronomy is about telescopes."
Edsger Dijkstra
Free beginner - intermediate level computer science tutorials
Tree Sort
Tutoring > Data Structures > Tree Sort
​Tree sort builds a binary search tree from elements in a given array. A binary search tree (BST) is an abstract data structrure such that:
-
The value of each node is greater than that of the left child
-
and smaller than that of the right child.
-
Each node has up to 2 children.
Average time complexity is O(n log (n))
Worst case time complexity is O(n^2) for an un-balanced tree or O(n log(n)) for a balanced tree.
As the tree is being built, rotations may have to be performed in order to maintain the properties of a balanced BST. The final result will be all of the elements from the input array in the form of a binary search tree.
We will make a balanced tree,
Ok, let us start with this array : {7, 3, 2, 8, 1, 6}
-
So the first element will be the root:
7
-
Next, insert 3 :
7
/
3
This is fine as it is still a BST.
-
Next, insert 2 as the left child of 3, this tree is now unbalanced.
7
/
3
/
2
-
So we need to perform a right rotation at 7, we bring the 3 and 2 up to their respective parent position and move the 7 to it's right child position :
3
/ \
2 7
This is now balanced again so we can insert the next node, 8 :
3
/ \
2 7
\
8
This is still ok, no rotations needed. Insert 1 :
3
/ \
2 7
/ \
1 8
This is also still ok oso insert the final element, 6 :
3
/ \
2 7
/ / \
1 6 8
This is all of the elements in the form of a BST. We can read the array in order by performing an in-order traversal.
1, 2, 3, 6, 7, 8