teaching machines

CS 240: Lecture 24 – Binary Trees

October 18, 2021 by . Filed under cs3, fall-2021, lectures.

Dear students:

We put the sorts behind us. Of course, nothing ever goes away in software development. We just put layers on top of it. Most of the time, we concern ourselves only with the outermost layer of abstraction: what are the methods named and what parameters do they expect? This class is meant to expose you to the inner workings of the tools that you will use throughout your career.

One data structure that hasn’t been abstracted away like lists and sorting algorithms have is the tree. The tree is often implemented as a linked structure. It’s like a linked list node, but it has multiple links to child nodes. When nodes have no more than two children, we have a binary tree. The linked node of a binary tree might look like this:

public class Tree<T> {
  T value;
  Tree<T> left;
  Tree<T> right;

There are many terms used to described the anatomy of a tree and the relationships it encodes. Let’s practice with a few of these:

How many nodes can appear at each depth? Drawing pictures helps answer this question. We see the following:

depth number of nodes
$0$ $1$
$1$ $2$
$2$ $4$
$3$ $8$
$4$ $16$
$5$ $32$
$\ldots$ $\ldots$
$i$ $2^i$

That leads to a couple of related questions, which we’ll work through as peer instruction exercises:

We’ll move away from the abstract view of trees into a concrete one by examining how they can be used to model arithmetic expressions. In particular, we’ll see what it takes to represent the expression 5 * 3 + 2 - 9 / 3 as a tree.


Occasionally we will need to visit all nodes in a tree, much as we visited all nodes in a list. The order in which visit nodes isn’t necessarily obvious. There are three ordering schemes that are common. An in-order traversal visits the left subtree, the root itself, and then the right subtree:


A post-order traversal visits the root after visiting its subtrees:


A pre-order traversal visits the root before visiting its subtrees:


We’ll examine each of these by writing routines for manipulating our expression trees and solving these problems:


You have some work to do before the next class:

See you next time.


P.S. It’s time for a haiku!

Are they binary?
One parent can’t make children
Except by forking