Cartesian tree

A Cartesian tree is a type of tree with special properties. It's named after the French mathematician René Descartes and is usually used for organizing data.

The tree starts with a single "root" node at the top. Each node on the tree holds a piece of data, like a number or a letter. We can then connect the nodes to form a tree. To make a Cartesian tree, each node is added in a special way. First, we connect the node to the root node. Then, if the new node's data (like a number) is bigger than the data in the root node, it becomes the root node's "right" child. If the new node's data is smaller than the root node's data, it becomes the root node's "left" child.

Each time we add a new node, we compare it to the other nodes to see if it should become the left or right child of a different node. This means that if we look at the tree from top to bottom, we can always see that the data of lower nodes is bigger than, or equal to, the data of their "parent" node. This is called the heap property of a Cartesian tree.

We use the structure of a Cartesian tree to quickly sort data and figure out which pieces of data are bigger or smaller than others.