Tree Traversals

Table of Contents

Based on Lenhart and Jannen (https://williams-cs.github.io/cs136-f20-www/slides/treeTraversals.pdf)

1 Reading

Get started on the lab early by reading the Lab 5 writeup before Friday.

2 Video

Here is a video lecture for today's lesson. Good supplementary reading can be found here.

The video contains sections on

  1. Learning goal (0:14)
  2. Initial example (1:16)
  3. Traversal motivation and pseudocode (4:28)
  4. Implementing traversals in Java (13:30)
  5. Level-order example (17:57)
  6. Level-order code (22:08)

The Panopto viewer has table of contents entries for these sections: https://carleton.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=4afb5b88-6eae-4099-b970-accb01653bed

3 Learning Goals

After this lesson you will be able to

  1. Describe and implement the four primary tree traverals

4 Slides

You can download the slides that were the basis for the video in pdf or PowerPoint.

5 Practice Problems1

  1. In code that recursively traverses binary trees, how many recursive calls are usually found within the code?

  2. For the following binary tree give the order nodes are visited for a pre-order, an in-order, a post-order traversal, and a level-order traversal.

    binary-tree.png

  3. What does this code do? 

    public void mystery(BinaryTreeNode<String> node) {
    if (node == null) {
        return;
    }
    mystery(node.right);
    mystery(node.left);
    System.out.println(node.data);
}
  4. Write a method public void printExpr(BinaryTreeNode<String> expr) that uses an in-order traversal to print out a correctly parenthesized version of the expression represented by the tree rooted at expr.

6 Learning Block

  • Summary
    • How to traverse the nodes in a binary tree?
    • 4 primary traversals:
      • pre-order: root, left, right
      • in-order: left, root, right
      • post-order: left, right, root
      • level-order: by depth, left to right
    • implemented the first three in very similar recursive methods
    • used a queue to implement level-order
  • Questions?
  • Form questions
  • Lab work time

Footnotes:

1

Solutions:

  1. Usually 2. Each call handles one subtree.
  2. When nothing else is said, a left-to-right traversal is assumed.
    • Pre-order traversal: GEBDFKMR
    • In-order traversal: BDEFGKMR
    • Post-order traversal: DBFERMKG
    • Level-order traversal: GEKBFMDR
  3. The code implements a right-to-left post-order traversal (i.e., the right subtree is traversed before the left subtree).
  4. public void printExpr(BinaryTreeNode<String> expr) {
    if (expr == null) {
        return;
    }
    if (expr.isLeaf()) {
        System.out.print(expr.data);
        return;
    }
    System.out.print("(");
    printExpr(expr.left);
    System.out.print(expr.data);
    printExpr(expr.right);
    System.out.print(")");
}