A Cartesian tree is a binary rooted tree data structure that can answer range queries can be answered by finding least common ancestors in the tree. It follows following properties:

- The Cartesian tree formed from a sequence has a node for each number in that sequence.
- An inorder traversal of the tree would give the original sequence used to form the tree.
- Follows the heap property, i.e. each node has value greater than its parent (min heap) or each node has value smaller than its parent (max heap).

**Read this article to understand Cartesian Tree in depth**

**Have a doubt or thought? Join the discussion now**

This is a companion discussion topic for the original entry at http://iq.opengenus.org/cartesian-tree/