# YOU CAN DOWNLOAD 200+ SUBJECTS PDF BOOK FOR COMPETITIVE EXAMINATIONS

## Data Structure Questions and Answers-Cartesian Tree

Question 1 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

What is a Cartesian tree?

a skip list in the form of tree | |

a tree which obeys cartesian product | |

a tree which obeys heap property and whose inorder traversal yields the given sequence | |

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?

true | |

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

both statements are true | |

only i. is true | |

only ii. is true | |

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?

it sorts partially sorted set of data quickly | |

it considers cartesian product of elements | |

it sorts elements in less than O(logn) | |

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?

use any tie-breaking rule between repeated elements | |

cartesian tree is impossible when repetitions are present | |

construct a max heap in such cases | |

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.