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, with bidirectional links connecting ''parent'' and ''child'' nodes, such that repeatedly following parent links, starting from any node, will always reach a unique ''root'' node. In a ''binary tree'', each node has 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). To construct the Cartesian tree for a given sequence of distinct numbers, set its root to be the minimum number in the sequence,<ref name=minmax>In some references, the ordering of the numbers is reversed, so the root node instead holds the maximum value and the tree has the max-heap property rather than the min-heap property.</ref> and [[recursion|recursively]] construct its left and right subtrees from the subsequences before and after this number, respectively. As a base case, when one of these subsequences is empty, there is no left or right child.{{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:
