Question

Consider a sequence of numbers to have repetitions, how a cartesian tree can be constructed in such situations without violating any rules?

(a) use any tie-breaking rule between repeated elements

(b) cartesian tree is impossible when repetitions are present

(c) construct a max heap in such cases

(d) construct a min heap in such cases

I'd like to ask this question from Cartesian Tree topic in section Binary Trees of Data Structures & Algorithms I

This question was posed to me by my school teacher while I was bunking the class.

Answer 1

Correct answer is (a) use any tie-breaking rule between repeated elements

To explain: Consider any of the tie breaking rules, for example the element which appears first can be taken as small among the same elements and then apply cartesian tree rules.