What is a Cartesian tree?
(a) a skip list in the form of tree
(b) a tree which obeys cartesian product
(c) a tree which obeys heap property and whose inorder traversal yields the given sequence
(d) a tree which obeys heap property only
My question is taken from Cartesian Tree topic in section Binary Trees of Data Structures & Algorithms I
I got this question in homework.
The correct option is (c) a tree which obeys heap property and whose inorder traversal yields the given sequence
The explanation is: A tree with heap property (parent is either small or big than children) and when traversed in inorder yields the given input sequence. refer below diagram question for clarity.