Class Test 2

Syllabus: From the Beginning till Heaps Date: 23rd October 2024, 6.30-7.30pm

Practice

a) convert max-heap → BST in $O(n)$: FALSE

• from what i see there is nothing standard to convert heaps to trees, but there are a lot of mentions to converting trees into heaps

// Converting Complete BST to special Max Heap
create an array of sorted elements by in-order-traversal 
by post order traversal replace all elements with the counter

prove: consider sorting

• create a heap from an array $O(n)$
• create a BST from the heap
• go inorder on the tree $O(n)$ now if step 2 was also $O(n)$ then we would have sorting in $O(n)$ which is not possible

b) find 2nd min in binary tree in $O(1)$. FALSE. Trick question c)