Cheers, let's suppose we have a MAX heap which does not allow duplicate elements. Is it possible for this heap to be a BST ? Choose the right answer(s) below:
Which one would be an appropriate answer ? I would choose (3) and (4), and my explanations for all I give as an answer. Thanks!
To start off:
A (max) heap is a complete binary tree, in which every node's value is larger or equal to its children's values.
A BST is a binary tree, where every node has up to 2 children and every node's value is larger than all the values of its left subtree, and smaller than all the values of its right subtree.
The heap I thought of was just have one value, e.g. 8. Since it has no children, this tree alone is only made up of its root. This tree is complete and the root's values are larger that those of its children so it's a heap. This tree is also a BST with no children. So there is a heap which is also a BST.
This is of course false. Let max heap be:
Of course this is a max heap, but not a BST since 6 is placed to the right of 8.
Ιncorrect, but we need to see (4) to prove it
Up to two nodes means that we can either have 0, 1 or 2 nodes.
If we have 0 nodes, it holds.
If we have 1 node, it also holds, we proved that.
If we have 2 nodes, it also holds. Let a max-heap with 2 nodes. For it to be max-heap it must be a complete tree, so by definition the second node should be placed to the left of the first node (root). By definition of the max-heap, the second node also contains values smaller than that of the first node (root). This is also tree for a BST with 2 nodes. So it's correct. Since (3) says only , (3) is incorrect.
(If anything is incorrect please point it out. Thanks!)
