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

Category: QuestionsConsider a sequence of numbers to have repetitions, how a cartesian tree can be constructed in such situations without violating any rules?
Editor">Editor Staff asked 4 weeks ago

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.

1 Answers
Editor">Editor Staff answered 4 weeks ago

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.