Cartesian Tree data structure

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