# Data Structure Questions and Answers-Cartesian Tree

## Data Structure Questions and Answers-Cartesian Tree

 Question 1 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
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
Question 1 Explanation:
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.

 Question 2 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
Is the below tree representation of 50, 100, 400, 300, 280 correct way to represent cartesian tree?
 A true B false
Question 2 Explanation:
A tree with heap property (parent is either small or big than children) and when traversed in inorder yields the given input sequence is called as a cartesian tree. as the above figure satisies both the properties. note that even min heap tree can be generated. the above is a max heap tree.

 Question 3 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
Which of the below statements are true

i.Cartesian tree is not a height balanced tree

ii.Cartesian tree of a sequence of unique numbers can be unique generated

 A both statements are true B only i. is true C only ii. is true D both are untrue
Question 3 Explanation:
A height balanced cartesian tree is not possible as seen in above question. also any time a unique sequnce possess a unique cartesian tree, this can be proven through induction.

 Question 4 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
What is the speciality of cartesian sorting?
 A it sorts partially sorted set of data quickly B it considers cartesian product of elements C it sorts elements in less than O(logn) D it is a self balancing tree
Question 4 Explanation:
It can sort a set which requires only some sorting or displacements. for example consider 78, 79, 80, 82, 81, 83, In this only 81 and 82 must be swaped to make it a complete sorted set, in this case cartesian sort comes to the rescue.

 Question 5 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
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
Question 5 Explanation:
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.

There are 5 questions to complete.