Cartesian tree

<p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, a Cartesian tree is a <a href="/facts/Binary_tree/TDV7GMpu">binary tree</a> derived from a sequence of distinct numbers. To construct the Cartesian tree, set its root to be the minimum number in the sequence, and recursively construct its left and right subtrees from the subsequences before and after this number. It is uniquely defined  as a <a href="/facts/Min-heap/A67B0K7L">min-heap</a> whose <a href="/facts/Tree_traversal/Dkch34pz">symmetric (in-order) traversal</a> returns the original sequence.
</p><p>Cartesian trees were introduced by Vuillemin (1980) in the context of geometric <a href="/facts/Range_searching/Fkls9MD3">range searching</a> data structures. They have also been used in the definition of the <a href="/facts/Treap/sNDcxCpE">treap</a> and <a href="/facts/Randomized_binary_search_tree/sNDcxCpE">randomized binary search tree</a> data structures for <a href="/facts/Binary_search/FFmQzunc">binary search</a> problems, in <a href="/facts/Comparison_sort/X1PvE50c">comparison sort</a> algorithms that perform efficiently on nearly-sorted inputs, and as the basis for <a href="/facts/Pattern_matching/CEwptMs9">pattern matching</a> algorithms. A Cartesian tree for a sequence can be constructed in <a href="/facts/Linear_time/77T62gmf">linear time</a>.
</p>

Cartesian tree open-in-new

Cartesian tree