Tree traversals

Pre-order, in-order and post-order, the outline method, expression trees and what each traversal is for.

A4.7Trees and graphsA level25 min

Breadth-first and depth-first traversal visit every vertex of a graph. A binary tree has three standard depth-first orders of its own, and each has its uses: printing a binary search tree in order, copying a tree, turning an expression into Reverse Polish notation. The three differ in only one thing: when each node is visited.

Three orders

Each traversal is recursive, and at every node it does three things: traverse the left subtree, traverse the right subtree, and visit the node itself. Only the position of the visit changes.

The name says where the node goes: pre, before its subtrees; in, in between them; post, after them. Left always comes before right.

For the binary search tree from the last lesson:

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def insert(node, key):
    if node is None:
        return Node(key)
    if key < node.key:
        node.left = insert(node.left, key)
    else:
        node.right = insert(node.right, key)
    return node

def preorder(node):
    if node is not None:
        print(node.key, end=" ")                  # visit first
        preorder(node.left)
        preorder(node.right)

def inorder(node):
    if node is not None:
        inorder(node.left)
        print(node.key, end=" ")                  # visit in between
        inorder(node.right)

def postorder(node):
    if node is not None:
        postorder(node.left)
        postorder(node.right)
        print(node.key, end=" ")                  # visit last

root = None
for marker in [17, 8, 31, 4, 12, 23, 40, 10]:
    root = insert(root, marker)

preorder(root)
print()
inorder(root)
print()
postorder(root)
print()

Run this in the simulator

The outline method

On paper there is a quick, reliable way to write a traversal down. Draw a line all the way round the tree, starting to the left of the root and going anticlockwise, so it runs down the left side first, hugging every node and every branch. Put a dot on each node:

• for pre-order, a dot on the node's left side;
• for in-order, a dot underneath the node;
• for post-order, a dot on the node's right side.

Follow the line and write each node down as the line passes its dot. It is also a good way to check a traversal you have traced by hand.

What each traversal is for

• Pre-order: copying a tree. Every node is visited before its children, so inserting the keys into a new, empty binary search tree in pre-order rebuilds exactly the same shape. Pre-order of an expression tree gives prefix, or Polish, notation.
• In-order: a binary search tree in ascending order. Everything to the left of a node is smaller and everything to the right is larger, so in-order visits the keys smallest first. Inserting data into a BST and then traversing it in-order is a sorting algorithm, the tree sort.
• Post-order: emptying a tree. A node is only visited after both its subtrees, so each node can be deleted once its children are gone. Deleting a folder works this way: its contents first, then the folder. Post-order of an expression tree gives Reverse Polish notation, so post-order is how an infix expression, once built into a tree, is converted to RPN.

Expression trees

An arithmetic expression is a binary tree. Each operator is an internal node with its two operands as subtrees, and each number is a leaf. The tree needs no brackets: its shape shows what is worked out first, because a subtree must be evaluated before the operator above it.

The in-order result has lost its brackets, and 2 + 3 * 4 is 14, not the tree's value of 20. A program that writes infix from a tree has to put brackets round each operator's subtree. Reverse Polish notation needs no brackets at all, and module A6 evaluates it with a stack.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

class Node:
    def __init__(self, item, left=None, right=None):
        self.item = item
        self.left = left
        self.right = right

EXPR = Node("*", Node("+", Node("2"), Node("3")), Node("4"))       # (2 + 3) * 4

def infix(node):
    if node.left is None:                         # a leaf: just the number
        return node.item
    return "(" + infix(node.left) + " " + node.item + " " + infix(node.right) + ")"

def rpn(node):
    if node.left is None:
        return node.item
    return rpn(node.left) + " " + rpn(node.right) + " " + node.item    # post-order

print(infix(EXPR))
print(rpn(EXPR))

Run this in the simulator

Working out the value of a tree is itself a post-order job: an operator can only be applied once both of its subtrees have values.

Breadth-first on a tree

Breadth-first traversal works on a tree as well, visiting it level by level from the root: 17, 8, 31, 4, 12, 23, 40, 10 for the marker tree. It uses a queue exactly as it does on a graph, and because a tree has no cycles it needs no visited marks.

Task: three ways round a tree

TREE holds the expression (5 - 1) * (2 + 3 * 4) as a binary tree of Node objects. Each node's item is an operator (+, - or *) or a single digit, both as strings, and a leaf has left and right set to None. Write recursive functions preorder(node), inorder(node) and postorder(node) that each return a list of the items in that order, and an empty list for None. Print pre-order:, in-order: and post-order:, each followed by that list's items separated by single spaces, one per line in that order. Then work out the value of the expression from the tree, without eval, and print value: followed by the whole number.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

class Node:
    def __init__(self, item, left=None, right=None):
        self.item = item
        self.left = left
        self.right = right

# (5 - 1) * (2 + 3 * 4)
TREE = Node("*", Node("-", Node("5"), Node("1")), Node("+", Node("2"), Node("*", Node("3"), Node("4"))))

def preorder(node):
    return []

Challenges

1. Write infix(node) for the task's tree, with brackets round every operator's subtree, and check it gives the same value as the original expression.
2. Draw the expression tree for 8 / (4 - 2) + 1 and write down all three traversals by hand. Which one is the RPN?
3. Evaluate the task's post-order list with a stack: push numbers, and on an operator pop two values and push the result. Does it match value?