Cartesian Trees are a type of data structure used in computer science for encoding a sequence of numbers.

From Wikipedia:

In computer science, a Cartesian tree is a binary tree derived from a sequence of numbers; it can be uniquely defined from the properties that it is heap-ordered and that a symmetric (in-order) traversal of the tree returns the original sequence.

[they’ve] also been used in the definition of the treap and randomized binary search tree data structures for binary search problems."

It’s an interesting, possibly obscure tree, but I found it fun to work on, especially as a way to create them more intuitively. I wrote an implementation of said tree in Python over at my personal project “Mother of All Learning” (MoAL), but as with most challenging things, I had to do a lot of back and forth on pen-and-paper to “grok” it. In the process of translating this concept into a tangible data structure that could actually be put to code, I found what I thought was a novel way to create the trees very simply, just by drawing.

Without further ado:

First, let’s look at an example: [9, 3, 7, 1, 8, 12, 10, 20, 15, 18, 5]

I find it’s easy to think of the list as being broken down into sub-lists, where each sub-list has a left, pivot, and right side.

With this in mind, we can find the pivot, which is always going to the smallest number, and then divide the list up into a sublist, where the first index is the current node, the second is the left child, and the third is the right. If left and right are empty, then the singleton list denotes a leaf.

Now, to visualize it, we use the above procedure, but for each pivot, draw a line up/down to the previous pivot, and then draw lines from the current pivot to the left and right children. At the end, you’ll get an actual tree drawing!

So, back to our example.

``9 3 7 1 8 12 10 20 15 18 5```

The first thing we need to do is find the pivot. As mentioned above, it’s always the smallest number. In this case, 1 is the pivot, so it becomes the root node, since all other elements will become leaves, and this is the first node.

      1
     / \
9 3 7   8 12 10 20 15 18 5

Ok, we’re getting somewhere. Now, for each new side, we need to do the same thing. So, on the left hand, 3 is the smallest, and on the right, 5 is the smallest.

      1
    /   \
  3      5
 / \    /
9   7  8 12 10 20 15 18

Visually, this is a bit odd because of spacing, but we can see all the numbers on the right branch (5) are to the left of 5 – it will look better once we finish it.

Next up is left, where there is nothing to be done, since each child of 3 is a leaf, and right, where 8 is smallest.

      1
    /   \
  3      5
 / \    /
9   7  8
        \
        12 10 20 15 18

And again, 10 is now the smallest.

      1
    /   \
  3      5
 / \    /
9   7  8
        \
        10
        / \
      12  20 15 18

And now, almost done, the right side is left; 15 is the smallest here.

      1
    /   \
  3      5
 / \    /
9   7  8
        \
        10
        / \
      12   15
          /  \
        20    18

And we’re done!

I find this is a fun way to solve the problem, although this isn’t easily (or efficiently) translated into code. For that, I follow the same procedure, but use nested lists, which can then be traversed the usual means, either a while loop, or recursively. Check out the implementation if you want to see more!