0
$\begingroup$

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:

  1. A heap can never be a BST
  2. A heap is always a BST
  3. A heap can be a BST if there is only one node inside it (root)
  4. A heap can be BST if and only if it has up to 2 nodes

Which one would be an appropriate answer ? I would choose (3) and (4), and my explanations for all I give as an answer. Thanks!

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

  1. 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.

  2. This is of course false. Let max heap be:

max-heap-but-not-bst

Of course this is a max heap, but not a BST since 6 is placed to the right of 8.

  1. Ιncorrect, but we need to see (4) to prove it

  2. 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!)

$\endgroup$
2
  • 1
    $\begingroup$ 3 is incorrect since its possible to construct a heap thats qlso a BST with 2 nodes. $\endgroup$
    – nir shahar
    Jun 19, 2021 at 15:08
  • $\begingroup$ @nir shahar Correct, thanks a lot for noticing that =) $\endgroup$ Jun 19, 2021 at 15:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.