Trees
Binary Trees
A binary tree is a data structure that is either empty or it consists of a root node with three pieces of data: a value (often a number or a string), and two subtrees, one on the left and one on the right. This can be expressed with the following recursive data type in Scala:1
enum Tree[+T]:
case Empty
case Node(left: Tree[T], value: T, right: Tree[T])
import Tree.*
def leaf[T](value: T): Tree[T] = {
Node(Empty, value, Empty)
}
val demo = Node(leaf(1), 2, Node(leaf(3), 4, leaf(5)))
// demo: Tree[Int] = Node(
// left = Node(left = Empty, value = 1, right = Empty),
// value = 2,
// right = Node(
// left = Node(left = Empty, value = 3, right = Empty),
// value = 4,
// right = Node(left = Empty, value = 5, right = Empty)
// )
// )
We use a type variable T as a parameter to specify the type of values in the tree.
The function leaf is a convenience, so that we can write leaf(1) for the tree with just the value 1 and two empty children instead of Node(Empty, 1, Empty).
In this case, it will infer that the type parameter T should be Int, so we get a Tree[Int].
Note the similarity to a list of type List[T], which is either an empty list or a list node with a head value
(of type T) and a sublist of the rest of the elements (the tail).
The natural way to write a function that takes a binary tree is to use (surprise) Pattern Matching, which corresponds to doing structural induction over the construction of the tree. For example, suppose we want to know how many nodes a tree has:
def size[T](t: Tree[T]): Int = {
t match
case Empty => 0
case Node(left, _, right) => size(left) + 1 + size(right)
}
size(Empty)
// res0: Int = 0
size(leaf("hello"))
// res1: Int = 1
size(demo)
// res2: Int = 5
If we have a list with integer values, we might want to get the total of all the values in the tree:
def total(t: Tree[Int]): Int = {
t match
case Empty => 0
case Node(left, value, right) => total(left) + value + total(right)
}
total(Empty)
// res3: Int = 0
total(demo)
// res4: Int = 15
A useful function on trees will be to have a visualization of the tree. Here is a simple rendering of a tree with Doodle:
val EMPTY_WIDTH = 5
val NODE_WIDTH = 20
val HSPACE = 10
val VSPACE = 30
// Compute the widths of the left and right subtrees of t
def showTreeWidths[T](t: Tree[T]): (Double, Double) = {
t match
case Empty => (EMPTY_WIDTH / 2, EMPTY_WIDTH / 2)
case Node(left, _, right) =>
val (ll, lr) = showTreeWidths(left)
val (rl, rr) = showTreeWidths(right)
(ll + lr + HSPACE, rl + rr + HSPACE)
}
def showTree[T](t: Tree[T]): Image = {
t match
case Empty => Image.circle(EMPTY_WIDTH).fillColor(Color.black)
case Node(left, value, right) =>
val showLeft = showTree(left)
val showRight = showTree(right)
val (_, lr) = showTreeWidths(left)
val (rl, _) = showTreeWidths(right)
val leftShift = lr + HSPACE
val rightShift = rl + HSPACE
val leftLine = Image.path(OpenPath.empty.lineTo(leftShift, VSPACE))
val rightLine = Image.path(OpenPath.empty.lineTo(-rightShift, VSPACE))
val leftImage = showLeft `on` leftLine
val rightImage = showRight `on` rightLine
Image.text(value.toString) `on`
Image.square(NODE_WIDTH).fillColor(Color.white) `on`
leftImage.originAt(Landmark.topRight) `on`
rightImage.originAt(Landmark.topLeft)
}
val treeDemo = showTree(demo)
Traversals
Processing a binary tree is often expressed as a traversal. There are several common tree traversals:
- Preorder: To process a non-empty tree, first process the value in its root node, then process the left child followed by the right child.
- Inorder: To process a non-empty tree, first process the left child, then the value in the root node, and finally the right child.
- Postorder: To process a non-empty tree, first process the left child, then the right child, and finish with the value in the root node.
- Level order: Process the value in the root node, then process the values in its children from left to right, then process its children's children from left to right, and so on, until there are no more nodes.
The first three traversals have very easy recursive implementations. For example, here is the preorder traversal,
which takes a Tree[T] and a function process: T => Unit (the return type of Unit is a sign that we are
expecting process to have a side-effect, such as printing, instead of returning a value):
def preOrder[T](t: Tree[T], process: T => Unit): Unit = {
t match
case Empty => ()
case Node(left, value, right) =>
process(value)
preOrder(left, process)
preOrder(right, process)
}
preOrder(demo, print)
// 21435
We will have to wait a bit to learn how to do the level order traversal.
To see an interesting connection between traversals and programming languages, we will consider a variation on binary trees called expression trees.
Expression Trees
An expression tree represents the structure of an expression.
This could be an arithmetic expression, such as , or a boolean expression such as ;
it also generalizes to expressions in a programming language, such as if a < b then c else d in Scala.
For now we will limit our consideration to expressions with boolean operators and integer operands,
which can be described by the following recursive type:
enum Expr:
case Const(c: Int)
case BinOp(left: Expr, op: String, right: Expr)
import Expr.*
val sample = BinOp(BinOp(Const(1), "+", Const(2)), "*", Const(3))
// sample: Expr = BinOp(
// left = BinOp(left = Const(c = 1), op = "+", right = Const(c = 2)),
// op = "*",
// right = Const(c = 3)
// )
Now we may define functions that perform preorder, inorder, and postorder traversals of expression trees to produce string representations of an expression:
def prefix(e: Expr): String = {
e match
case Const(n) => n.toString
case BinOp(left, op, right) =>
String.format("%s(%s, %s)", op, prefix(left), prefix(right))
}
def infix(e: Expr): String = {
e match
case Const(n) => n.toString
case BinOp(left, op, right) =>
String.format("(%s %s %s)", infix(left), op, infix(right))
}
def postfix(e: Expr): String = {
e match
case Const(n) => n.toString
case BinOp(left, op, right) =>
String.format("%s %s %s", postfix(left), postfix(right), op)
}
prefix(sample)
// res7: String = "*(+(1, 2), 3)"
infix(sample)
// res8: String = "((1 + 2) * 3)"
postfix(sample)
// res9: String = "1 2 + 3 *"
The preorder traversal of an expression tree gives the prefix form of the expression, where the operator comes in front of both of its operands.
With the extra parentheses and commas added above, you can see that this is our familiar function call notation: +(1, 2) is just the application of the addition function to the arguments 1 and 2.
The inorder traversal of an expression tree gives the infix form of the expression, where the operator takes its usual position between its operands.
The extra parentheses are essential here, to avoid the ambiguity of whether 1 + 2 * 3 is an addition of 1 and 2 * 3, or whether it is a multiplication of 1 + 2 by 3.
In practical use we get around this by adopting conventions of precedence, saying for example that multiplication takes precedence over addition, so that 1 + 2 * 3 has an addition operator at the root.
In the sample expression tree, however, the multiplication is at the root, so we have to insert at least one pair of parentheses to get the correct expression: (1 + 2) * 3.
The postorder traversal of an expression tree gives the postfix form of the expression, which may not be as familiar. Back in the Dark Ages2 of computing, Hewlett-Packard made a series of powerful calculators that became very popular, particularly with engineers. At the time, calculators were not able to handle arbitrarily complex infix expressions (many of them didn't even have parentheses…), and HP's solution was elegant: use postfix instead of infix! They referred to this as Reverse Polish Notation (RPN) in honor of the logician Jan Łukasiewicz (1878–1956), who invented postfix in the 1920's as a way to write logical expressions without parentheses.
The key to interpreting a postfix expression is to imagine maintaining a stack of values as you read from left to right.
When you see a number, push that value onto the stack.
When you see an operator, since it must be following its two operands, pop two values from the stack, perform the operation, and push the result back on the stack.
For the sample above, 1 2 + 3 *, you can check that the resulting value on the stack at the end of the expression is the expected 9.
More recent uses of postfix expressions and stack-based evaluation are the PostScript page description language used by many printers (which also forms the basis of the PDF document format), and the Java Virtual Machine code produced by the Java compiler.
Exercises
- Write a Scala function
height[T](t: Tree[T]): Intthat computes the height of the treet. We define the height of an empty tree to be 0, and the height of a node is one more than the larger of the heights of its children. In Scala, the binary operatora max bcomputes the maximum ofaandb.