Trees: terminology, binary trees and traversals

Lists, stacks and queues (SEN2211) were linear structures: each element had at most one “next”. A tree is a hierarchical structure: an element can have many “children”. File systems, HTML documents, a compiler’s expression trees and database indexes are all trees. The next six weeks of this course (BST, AVL, red-black, heap) build on the terms on this page.

The questions from this week in the exam are: terminology (depth, height, number of leaves in a given tree), traversal traces (preorder, inorder, postorder, level-order), expression trees (build from postfix, evaluate) and building a tree from two traversals.

Terminology

Let’s take this general tree as our example:

            A
         /  |  \
        B   C   D
       / \     / \
      E   F   G   H
              |
              I

Two basic facts: a tree with n nodes has n - 1 edges (every node except the root has exactly one parent edge). There is exactly one path from the root to any node.

PITFALL · depth and height are measured in opposite directions. Depth goes top to bottom (the root has depth 0), height goes bottom to top (a leaf has height 0). Some sources count nodes, not edges. In this course and in Weiss we count edges; the height of an empty tree is -1.

Storing a general tree: first-child, next-sibling

If you do not know how many children a node will have, you cannot put a fixed number of references in each node. The solution: keep two references in each node, the first child and the next sibling on the right.

class TreeNode {
    String element;
    TreeNode firstChild;   // leftmost child
    TreeNode nextSibling;  // sibling to the right
}

In the tree above, A.firstChild = B, B.nextSibling = C, C.nextSibling = D, D.firstChild = G. This representation actually turns any general tree into a binary tree.

For a general tree, preorder (the node first, then its children from left to right) and postorder (the children first, then the node) are defined:

preorder : A B E F C D G I H
postorder: E F B C I G H D A

File system example: printing a directory listing with indentation is preorder; computing the total size of a directory is postorder (you need the sizes of the subdirectories first).

Binary trees

In a binary tree every node has at most two children, and the children are distinguished as left and right. A node that has only a right child is a different tree from one that has only a left child.

class Node {
    int element;
    Node left, right;
    Node(int e) { element = e; }
}

Special kinds of binary trees

The complete tree will be the shape of a heap in week 7. The important numbers:

$\text{at most } 2^{h+1} - 1 \text{ nodes for height } h, \qquad h \ge \lfloor \log_2 n \rfloor \text{ for } n \text{ nodes}$

In the worst case (every node has a single child) the height is $n - 1$ and the tree degenerates into a linked list. Since the running time of tree operations depends on the height, keeping the tree short is the main theme of the coming weeks.

Traversals

Let’s trace the four traversals on this binary tree:

          A
        /   \
       B     C
      / \     \
     D   E     F
        /     / \
       G     H   I

The code is three lines; only the position of the “visit” line changes:

static void preorder(Node n) {
    if (n == null) return;
    visit(n);              // first
    preorder(n.left);
    preorder(n.right);
}
static void inorder(Node n) {
    if (n == null) return;
    inorder(n.left);
    visit(n);              // in the middle
    inorder(n.right);
}
static void postorder(Node n) {
    if (n == null) return;
    postorder(n.left);
    postorder(n.right);
    visit(n);              // last
}

Level-order is not recursive; it uses a queue: put the root in the queue, and at each step remove from the front, visit, and add its children (left first) to the back.

static void levelOrder(Node root) {
    Queue<Node> q = new ArrayDeque<>();
    if (root != null) q.add(root);
    while (!q.isEmpty()) {
        Node n = q.poll();
        visit(n);
        if (n.left != null) q.add(n.left);
        if (n.right != null) q.add(n.right);
    }
}

All four visit each node once: $O(n)$ time. The recursive ones use $O(h)$ stack memory; level-order uses queue memory as large as the widest level.

TIP · the hand-traversal trick. Imagine a line that starts on the left and walks counterclockwise around the tree. If you write a node when the line touches its left side, you get preorder; when it touches the bottom, inorder; when it touches the right side, postorder.

Expression trees

In an expression tree the leaves are operands (numbers or variables) and the internal nodes are operators. (3 + 4) * (5 - 2):

          *
        /   \
       +     -
      / \   / \
     3   4 5   2

• postorder → postfix: 3 4 + 5 2 - *
• preorder → prefix: * + 3 4 - 5 2
• inorder + parentheses → infix: ((3 + 4) * (5 - 2))
• value: evaluate in postorder: first the two subtrees, then the operator → 7 * 3 = 21

Building a tree from postfix

It is the same as the postfix evaluation algorithm from SEN2211, but you push nodes instead of numbers:

1. If an operand arrives, make a single-node tree and push it.
2. If an operator arrives, pop the right subtree first, then the left, make an operator node, and push it.
3. At the end exactly one tree is left on the stack.

The stack state for 6 2 / 1 + 4 *:

6        -> [6]
2        -> [6, 2]
/        -> [(6/2)]
1        -> [(6/2), 1]
+        -> [((6/2)+1)]
4        -> [((6/2)+1), 4]
*        -> [(((6/2)+1)*4)]     value 16

Building a tree from two traversals

Preorder (or postorder) tells the root, and inorder separates left from right. The algorithm:

1. The first element of the preorder is the root.
2. Find the root in the inorder. What is to its left is the left subtree, what is to its right is the right subtree.
3. In the preorder, the next elements after the root, as many as the left subtree has, are the left subtree’s preorder; the rest is the right’s.
4. Repeat for each subtree.

Example: preorder A B D E C F, inorder D B E A F C.

root A      inorder: [D B E] A [F C]
left: pre B D E, in D B E -> root B, left D, right E
right: pre C F,   in F C   -> root C, left F

        A
       / \
      B   C
     / \  /
    D  E F
postorder: D E B F C A

The same is done with postorder + inorder; this time the root is the last element of the postorder.

Common mistakes

          K
       /  |  \
      L   M   N
     / \      |
    O   P     Q
            / | \
           S  T  U

        1
       / \
      2   3
     /   / \
    4   5   6
     \     /
      7   8

        1
       / \
      2   3
     /   / \
    4   5   6
     \     /
      7   8

static int countLeaves(Node n) {
    if (n == null) return 0;
    if (n.left == null && n.right == null) return 1;
    return countLeaves(n.left) + countLeaves(n.right);
}

static int height(Node n) {
    if (n == null) return -1;
    return 1 + Math.max(height(n.left), height(n.right));
}