What is a Cartesian tree?

Category: QuestionsWhat is a Cartesian tree?
Editor">Editor Staff asked 1 month ago

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
Editor">Editor Staff answered 1 month ago

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.