Question

a) We have discussed level-filled binary and BST: both are rooted trees. What is the main

difference between level-filled binary and BST?

b) We have discussed two data structures heap and BST. They have similarities and

differences. List two similarities and two differences between BST and heap

c) Give a situation where BST can be fully unbalanced

Answer 1

a)Main difference between the two is filling of data inside these two trees i.e in BST the data is ordered(left sub-tree contains nodes with data lesser in value of root node and right sub-tree contains nodes with data greater in value than value of root node).As in case of level filled data is filled irrespective of these constraints.Also in BST, left and right sub-tree are also BST in nature.

b)

i)Similarities Between Heap And BST:

1.Both follows a certain pattern.

2.For a special case(pattern of left to right increasing node value) heap is BST only.

3.Both are of good use for searching algorithms.

i)Difference Between Heap And BST:

1.Heap Guarantees that the elements on higher level are greater and on the lower level are smaller, While BST does the same while going from left to right.

2.heap is best for finding min/max (O(1)),whereas BST is good for all searches(O(log(n))).

c) Max Heap and Min Heap can act as A fully unbalanced BST because in both cases the value differs from top to bottom whereas in BST the value differs from left to right.the time to convert both of them to BST is huge and works as Fully unbalanced BST.