Trees!

I really like trees. Both the growing kind, and the computer science kind. Remember Linked Lists? A bunch of cells strung together to form a chain, where each cell has a pointer to the next cell? Trees are almost the same idea.

Picture this: A cell with a ‘left’ pointer and a ‘right’ pointer. Instead of just being able to follow along the chain, the chain branches. This makes a structure like this:


4

/ 11 2 / 7 5 9 —-

Some terminology: Each number is a node. The height of the tree is how deep it is (3). The root of the tree is the topmost node (4). The ones on the bottom are called leaves.

What is this useful for? Actually, a lot of things. For example, file-systems are trees. There’s a root directory (/ or C:\), and descending from the root, there’s a system of other directories, and files. Trees are also used for storing data that needs to be ordered, or that depends on other data.

One common use for trees is representing mathematical expressions.


+

/ * / 3 5 9

This represents 9 + 3*5. Pure mathematical expressions aren’t the only thing that can be represented, though. Take, for example:


define / fact * / / n n fact - / n 1 —-

This represents a piece of code:


def fact(n): return n * fact(n – 1) —-

Note: This code doesn’t work and runs forever. To make it terminate, you would need to include a condition that fact(0) = 1

These kinds of trees are called Expression trees or Abstract Syntax Trees. They’re the most common way for compilers and other programs that deal with source code to represent programs internally. Representing programs like this makes them simple to execute: evaluate the left, the right, and then do what the node says.

There are other uses of trees - binary search trees, hash trees, etc. - but that’s the overview. See you again next week!