Rust: Binary Tree
Building and Collapsing Expression Trees
Since Rust has become so wildly popular and has amassed such a dedicated following, I decided to put down my beloved JS and learn Rust recently. And I must say, it’s not a journey for the faint of heart. Luckily (although misleading in some rare occasions) the compiler is your best friend — it will nearly always tell you what you did wrong, and will even offer helpful solutions. After you spend some time with it and get over the steep initial learning curve, you’ll begin to love Rust — I do!
Today I’d like to implement my favorite data structure, in Rust flavor: the Binary Tree. A Binary Tree is a typical tree — it consists of Nodes that hold it’s (potentially deeply) nested values. The special thing about a Binary Tree is that its nodes have only two child values: a Left and a Right. Typically, Binary Trees are used to represent things like mathematics expressions, but could be used to handle parsing lightweight grammars. For our implementation it will also be convenient for our nodes to know what type of operation they represent. We’ll try to make it generic so as to make the underlying structure type-agnostic. Here’s a simple representation of a Binary Tree:
The terminal nodes have numbers in them in this image. It’s also good to note that Binary Trees are left-biased and depth first in ordinance. That means that when you collapse a binary tree, the evaluation will descend into the first left node as deep as it can before moving to righter nodes, and those nodes’ left nodes before its righter nodes, etc., recursively. I’ll explain a bit more as I go.
Let’s imagine a minimal struct to represent our Node data:
…and the compiler is mad at us right away. A struct cannot contain references to itself directly (it becomes a recursive type which is illegal in Rust). But conveniently, we can put our recursive nodes in a Box. A Box is just a fancy way to say, ‘this is a pointer that references an…
