Trees

Summary

We consider trees, a way of organizing information hierarchically. Like lists, trees have a straightforward (but recursive) definition and a variety of applications. And, as in the case of lists, you may find it useful to think about how trees are implemented.

Introduction

In this reading, we explore issues related to trees, including some terminology for talking and writing about trees, some formal definitions of trees, some techniques for recursion over trees (using what is often called deep recursion), and some applications.

Tree basics

As you know, a list is a collection of values in which each value has at most one successor. (Every value but the last value has one successor; the last value has no successor.) While lists are useful for a wide variety of situations, there are situations in which they do not suffice. One is the problem of modeling a hierarchy. For example, the president of a company may have two vice presidents who report to him, her, zir, or them; each vice president may have assistant vice presidents who report to them; and so on and so forth.

We use the term tree for structures in which each value may have multiple successors (or underlings, as in the example above). When each value may have at most two successors, we call them binary trees. In this reading, we will focus primarily on binary trees. Here’s a sample binary tree written in the way that many computer scientists make them.

There are a number of important characteristics we associate with binary trees, including

• the root of a tree, which refers to the top of the tree;
• the size of a tree, the number of values stored in the tree;
• a path is a sequence of values in the tree connected by arrows;
• the depth of a tree, the length of the longest path from the top of the tree to the furthest value; and
• the base type of the tree, which indicates what kind of values the tree is built from. We call trees that have no single base type heterogeneous trees.

At any point in the binary tree built we usually refer to the two trees below it as the left subtree and the right subtree. We refer to the equivalent of a pair as a node. When both of the subtrees of a node are empty, we call that node a leaf.

In the sample tree, the root value is “John”, its left subtree is rooted with “Henry” and its right subtree is rooted with “Sam”. The size of the tree is nine because there are nine values in the tree. The depth of the tree is five for the John -> Sam -> Marge -> PM -> Rhys path. The leaves are Charlie, Janet, and Rhys.

As you may have noted, trees represent hierarchies. You may recall that XML documents are also hierarchical, which means that we can represent them as trees. Here’s a more complex tree, based on the structure of an XML document.

[Forthcoming]

Formalizing trees

We have an informal definition of trees, given by the figure above. Can we define them formally? Yes. Just as we can define lists recursively, so can we define trees recursively. As you may recall, the definition of a list goes something like the following:

• The empty list (null) is a list.
• If lst is a list and val is any Scheme value, then (cons val lst) is a list.
• Nothing else is a list.

Why do we call this a “recursive definition”? Because the definition of a list is in terms of lists (at least in the middle item). We can write a similarly recursive definition for trees. We’ll write one for binary trees, in which each value has two successors, rather than the one successor in lists.

• The special value empty is a binary tree.
• If t1 and t2 are binary trees, and val is any Scheme value, then
  (node val t1 t2) is a binary tree.
• Nothing else is a binary tree.

If all of the values have the same type, then we can refer to the tree in terms of the type name. For example, if all of the values are numbers, we would call it a “number tree”.

Similarly, we can formalize XML documents as follows.

[FORTHCOMING]

Applications of trees

Computer scientists have found a wide variety of applications of binary trees and more general trees. As we suggested at the beginning of the reading, a general tree can provide a way to represent the hierarchy of positions at the organization. At the top of the tree we have the President or CEO. Beneath the President are the Vice Presidents. Beneath each Vice President are Deans or Directors. And so on or so forth.

However, there’s little you can do with a tree representing a hierarchy than try to find where someone belongs in the hierarchy. Hence, we use trees for a variety of other applications.

As its name suggests, a decision tree represents a series of decisions, such as yes/no questions. We might have the left branch correspond to a “yes” answer and the right branch correspond to a “no” answer. Here is a text-based decision tree to help students select a course.

Have you taken a course in computer science?
  N: Are you interested in learning to program?
     N: We recommend that you take CSC 105, in which you consider social issues in computing.
     Y: We recommend that you take CSC 151, in which you consider both programming issues and more general social issues.
  Y: Did you take CSC 151 or an equivalent course?
     N: Did you enjoy the course?
        N: We recommend that you take CSC 151; it presents a different view you might enjoy.
        Y: We recommend that you take CSC 151.  You'll learn new things.
     Y: We recommend that you talk to a faculty member.

We also use forms of binary trees called binary search trees. In binary search trees, everything in the left subtree is smaller than the root (in a tree of strings, everything in the left subtree comes alphabetically before the root) and everything in the right subtree is larger than the root (in a tree of strings, everything in the right subtree comes alphabetically after the root).

Patterns of tree recursion

As you should recall from our initial explorations of recursion, there is a traditional pattern for recursion over lists:

(define recursive-proc
  (lambda (lst)
      (if (null? lst)
          (base-case)
          (combine (car lst)
                   (recursive-proc (cdr lst) other)))))

We chose this pattern because of the common definition of a list. Because a list is either null or the cons of a value and a list we have two cases: one for when the list is null and one for the cons case. Since the cdr of a list is itself a list, in makes sense to recurse on the cdr.

A binary tree, in comparison, is either the empty tree or a node. If it’s a node, it contains a value and two successors. Hence, we will need to recurse on both halves, as well as look at the value in the node.

(define tree-proc
  (lambda (tree)
      (if (empty? tree)
          (base-case other)
          (combine (contents tree)
                   (tree-proc (left tree))
                   (tree-proc (right tree))))))

We can use this pattern to count the number of values in a tree.

(define tree-size
  (lambda (tree)
    (if (empty? tree)
        0
        (+ 1 
           (tree-size (left tree))
           (tree-size (right tree))))))

We can also use this pattern to find the depth of a binary tree. In this case, the depth of the empty the tree is 0, and the depth of any other tree is one higher than the depth of its largest subtree.

(define tree-depth
  (lambda (tree)
    (if (empty? tree)
        0
        (+ 1 (max (tree-depth (left tree))
                  (tree-depth (right tree)))))))

We can use a variant of this pattern to search the tree for a value.

(define tree-contains?
  (lambda (tree val)
    (cond
      [(empty? tree)
       #f]
      [(equal? (contents tree) val)
       #t]
      [(tree-contains? (left tree) val)
       #t]
      [(tree-contains? (right tree) val)
       #t]
      [else
       #f])))

Of course, if we find ourselves writing that many explicit #t and #f, we should probably rewrite it using the Boolean operations.

(define tree-contains?
  (lambda (tree val)
    (and (not (empty? tree))
         (or (equal? (contents tree) val)
             (tree-contains? (left tree) val)
             (tree-contains? (right tree) val)))))

You will note that we always use direct recursion, rather than helper recursion. That’s because it’s very difficult to express recursion on both subtrees using helper recursion.

Self checks

Check 1: Tree recursion patterns

Recall the pattern for tree recursion.

a. Identify the base case and combination of both tree-size and tree-depth.

b. Relate the two pieces for each function. How is the base case value related to (or working with) the combination step for each function?

c. Contrast the values of each of these pieces between the two functions. How and why do the base cases differ? How and why do the combinations differ?