As a detailed example of a tree used to model a particular domain, we will consider expression trees. An expression tree is a binary tree (max of two children per node) that represents a mathematical expression. Each internal node stores an operator (like +, -, *, /) and each leaf node stores an operand (a number).
The root of the expression tree represents the last operation to be performed. Its children represent the sub-expressions that are the inputs to that operation. We must compute \(8 - 2\) and \(1 + 4\) and then multiply their results. In traditional math notation we would use parentheses to show that those operations need to be performed first. The expression tree makes the order of operations explicit by the structure of the tree itself.
Most algorithms on a tree involve some form of traversal - visiting each node in the tree in a particular order. There are a few common ways to traverse a tree. One way is called pre-order traversal, where when we visit a node, we first process the node itself, then recursively visit its left child, and then recursively visit its right child.
In a post-order traversal, when we first enter a node, we recursively visit its left child, then recursively visit its right child, and only then process the node itself.
It is convention in both forms of traversal to visit the left child before the right child. For some algorithms the order will not matter, but for others it will be important to pick a direction and be consistent. For example, in our expression tree, we need to know if the subtraction node is calculating \((8 - 2)\) or \((2 - 8)\text{.}\) By sticking to a consistent left-right order, we can be sure that the left child is always the first operand and the right child is always the second operand.
Pre and Post refer to the timing of when the node itself is processed relative to its children during a traversal. Pre (before) means the node is processed before its children, and Post (after) means the node is processed after its children.
In a binary tree, there is also another common traversal called in-order traversal. In this traversal, when we visit a node, we first recursively visit its left child, then process the node itself, and finally recursively visit its right child. In an expression tree, an in-order traversal will produce the expression in its traditional infix notation (with parentheses to indicate order of operations).
The expression tree for \((8 - 2) * (1 + 4)\) is shown below. Use the buttons to step through pre-order, in-order, and post-order traversals of the tree.
You can click and drag on the animation area to pan around. Use the Ctrl + mouse wheel (or touchpad scroll gesture) while over the animation area to zoom in and out.
Notice that in pre-order, the first item is always the root of the tree. Then comes its left child, followed by the left child’s subtree, then the right child and its subtree. In post-order, the first item is always the leftmost leaf node. The root of the tree is always the last item in post-order.
Part of deciding how to implement an algorithm on a tree is deciding which traversal to use. For example, to evaluate an expression tree (calculate the result of the expression it represents), we would want to use a post-order traversal. We need the result of the left and right sub-expressions before we can apply the operator at the parent node. In post-order traversal, we will always visit the children before the parent, so we can calculate the values of the children first and then use them to calculate the value of the parent. Click the Evaluate Expression button in the interactive above to see this in action.
