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.

1 Answers

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.