Cartesian trees are defined using [[binary tree]]s, which are a form of [[rooted tree]]. These are mathematical structures rather than computer [[data structure]]s, although Cartesian trees have been used as part of the definition of certain data structures. A ''rooted tree'' consists of a collection of nodes, connected bywith bidirectional links connecting ''parent'' and ''child'' nodes, with the property that repeatedly following parent links, starting from any node, will always reach a unique ''root'' node. In a ''binary tree'', each node may have at most two children, designated as its left and right child. As well, each node may have some associated data (a number, in the case of a Cartesian tree). A Cartesian tree for a given sequence of distinct numbers may be defined [[recursion|recursively]]. Its root node is associated with the minimum number in the sequence.<ref>In some references, the ordering of the numbers is reversed, so the root node instead holds the maximum value.</ref> The left child of the root is the root node of a Cartesian tree constructed in the same way for the subsequence of numbers to the left of the minimum, before it in the sequence. And the right child of the root is the root node of a Cartesian tree constructed in the same way for the subsequence of numbers to the right of the minimum, after it in the sequence. If the left or right subsequence is empty, there is no left or right child, respectively.{{sfnp|Vuillemin|1980}}
It is also possible to characterize the Cartesian tree directly rather than recursively, using its ordering properties. In any tree, the ''subtree'' rooted at any node consists of all other nodes that can reach it by repeatedly following parent pointers. The Cartesian tree for a sequence of distinct numbers is defined by the following properties:
