Question

We can sort a given set of n numbers by first building a binary search tree containing these numbers (using Tree-Insert repeatedly to insert the numbers one by one) and then printing the numbers by an inorder tree walk. What are the worst-case and best-case running times for this sorting algorithm?

Answer 1

Worst case for binary search tree -O(n)

Best case for binary search tree -O(1)

Explanation:

The Binary search tree is the special type of binary tree. There are two child node

1. Left child node
2. Right child node  

• In that, the right child node has a value greater than it’s the parent node. The left child node has value less than it’s the parent node.
• In the below fig. for inserting element 0, it must be inserted as the left child of 1. Therefore, for sorting we have traveled in reverse order from (3,2,1) this is the worst-case complexity O(n).