Use tree in-order traversal to determine whether a BST or Heap

Question

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?

Answer 1

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