Tree Traversals

In this lesson, we will think about how to traverse over a tree in a pre-defined, standard way.

All of the previous data structures that we have considered were linear, and iterating over a linear data structure has an obvious beginning and end. However, with a tree, the order in which we visit the nodes of the tree in an algorithm is not obvious. For example, consider the following tree:

One way of traversing this tree would be in level-order: the nodes are visited one level at a time, from top to bottom. A level-order traversal would therefore visit the nodes in the order 1 2 3 4 5 6 7 8 9.

However, we've already written an algorithm that does not visit the nodes in level-order! The num_nodes() method from the previous lesson, for example, accounted for the root node in the count, then recursively visited the left subtree, and then recursively visited the right subtree:

def __num_nodes(self, node):
    if node is None:
        return 0

    return 1 + self.__num_nodes(node.left) + self.__num_nodes(node.right)

For the above tree, __num_nodes() would have visited the nodes in the order 1 2 4 5 7 8 3 6 9.

Often, it does not matter the order in which the nodes are visited. For some scenarios, such as evaluating an algebraic expression that is modeled as a tree, the order does matter. Therefore, there are some well-known traversal orders, described below.

Pre-order traversal

To summarize, a pre-order traversal of a binary tree first visits the current node, then visits the current node's left subtree, and then recursively visits the current node's right subtree:

def __preorder_print(self, cur):
    if cur is None:
        return

    print(cur.val)
    self.__preorder_print(cur.left)
    self.__preorder_print(cur.right)

def preorder_print(self):
    self.__preorder_print(self.root)

In-order traversal

An in-order traversal of a binary tree first visits the left subtree recursively, then visits the current node, and then visits the right subtree recursively:

def __inorder_print(self, cur):
    if cur is None:
        return

    self.__inorder_print(cur.left)
    print(cur.val)
    self.__inorder_print(cur.right)

def inorder_print(self):
    self.__inorder_print(self.root)

Post-order traversal

An post-order traversal of a binary tree first visits the left subtree recursively, then visits the right subtree recursively, and then visits the current node:

def __postorder_print(self, cur):
    if cur is None:
        return

    self.__postorder_print(cur.left)
    self.__postorder_print(cur.right)
    print(cur.val)

def postorder_print(self):
    self.__postorder_print(self.root)