0
$\begingroup$

Given these in-order traversal lists:
1. 53, 1, 64, 23, 3, 29, 17, 2, 9, 19
2. 49, 32, 51, 71, 32, 10, 21, 8, 13, 11, 41, 17

I need to determine whether each one of those lists represent a valid BST / min or max heap, or none.
I was trying to figure how to approach this, but besides brute-forcing every possible option I couldn't figure a "smart" way to solve this.

What indicators can I use, if there are any, or the way to solve this would be literally brute forcing every option?

$\endgroup$
0
1
$\begingroup$

None of them can be a BST. An in-order traversal of a BST visits the vertices in non-decreasing order of their keys (this is easy to prove by induction).

To determine if they are heaps, notice that by the number of elements in the list you already know the topology of the tree (heaps are completely binary trees up to the one-to-last level, and all the leaves on the last level are packed on the left side). Then the exercise boils down to writing down the given keys in the same order of the traversal and checking if the heap property holds.

In the specific example the first sequence cannot be a in-order traversal of a heap since the resulting tree would have a path with keys $23, 1, 53$ (in increasing order of depth). The same argument applies to the second sequence for a path with keys $71, 32, 49$.

$\endgroup$
3
  • $\begingroup$ Even without the "completness" contraint, you can check if it's a (non balanced) min heap by finding the root (the minimum) and check if the sublists left and right of this element correspond to min heaps. $\endgroup$ – Tassle Jun 13 '20 at 15:38
  • $\begingroup$ A heap requires the tree to be "almost complete" by definition. If it's "non balanced" it is not an heap. $\endgroup$ – Steven Jun 13 '20 at 15:39
  • $\begingroup$ Right, I thought there was some weaker notion of heap but apparently it's not standard. $\endgroup$ – Tassle Jun 13 '20 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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