Stack-based VMs, like SQLite's (I think), ARE trees. A stack based VM's bytecode (without DUP and POP) is just the post-order depth-first traversal of the corresponding expression tree. With DUP you have a connected acyclic DAG. With POP you have an acyclic DAG with one or more components. With loops you have a full graph.

When looked at this way, a VM makes the most sense actually because a pointer-heavy tree implementation is just terrible for caching and is super wasteful. Also, most SQL plans are trees (Until you get to WITH RECURSIVE).

I'm working on a CEP in C right now and a stack-based bytecode is simply the most 'obvious' way to represent a tree when you don't want to have to deal with lots of memory allocations. Just pre-allocate a buffer large enough and increment and go.

Either way, try taking something like the following and printing an expression tree like the one below

  LITERAL 2
  LITERAL 3
  LITERAL 4
  MUL
  PLUS

now, write something to produce on a terminal, the following:

  Plus
    Mul
      3
      4
    2

You should be able to do this in a simple iteration through the ops. Try it! Then try it with the variations above.

Now, try writing ops to manipulate and rewrite it. It's actually really a fun way to represent trees.