Suppose n unsorted elements are in a “binary search tree”, defined as a binary t
ID: 3667428 • Letter: S
Question
Suppose n unsorted elements are in a “binary search tree”, defined as a binary tree in which the keys in the left and right children are respectively smaller and larger than the key in their parent node. Describe how to sort the data, using auxiliary BSTs as necessary. What is the time complexity of your algorithm?
Suppose n unsorted elements are in a “heap”, defined as a binary tree in which the keys in the left and right children are both larger than the key in their parent node. Describe how to sort the data, using auxiliary heaps as necessary. What is the time complexity of your algorithm?
Given the various possible shapes of a binary tree, what are the best, average and worst case number of operations for “preorder” traversal? Why?
Explanation / Answer
Insert all data into Binary Search Tree and then do INORDE traversal. You will get dorted data.
Time Complexity = O(n). This worst case happen when BST is Left Skew(only left child for each node) or Right Skew Tree.
When you use Heap DataStructure, To get the sorted data, first build Min Heap and the extract root(minimum item) one by one.
Time Complexity for Heap = O(nlogn)
For preorder traversal, for any shaped binary tree it will be O(n), because you have to go through all items(n), so it does not depends on shape. So, worst, average, best = O(n)