Learn Computer Science

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:

1. The value of each node is greater than that of the left child

2. and smaller than that of the right child.

3. Each node has up to 2 children.

 

More on trees. 

 

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