Question

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

Answer 1

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.