5.5 Binary Tree Traversals

Often we wish to process a binary tree by “visiting” each of its nodes, each time performing a specific action such as printing the contents of the node. Any process for visiting all of the nodes in some order is called a traversal. Any traversal that lists every node in the tree exactly once is called an enumeration of the tree’s nodes. Some applications do not require that the nodes be visited in any particular order as long as each node is visited precisely once. For other applications, nodes must be visited in an order that preserves some relationship.

A binary tree for traversal examples.

5.5.1 Preorder Traversal

For example, we might wish to make sure that we visit any given node before we visit its children. This is called a preorder traversal.

Example: Preorder enumeration

The preorder enumeration for the tree of Figure #BinTravExample is A B D C E G F H I.

The first node printed is the root. Then all nodes of the left subtree are printed (in preorder) before any node of the right subtree.

5.5.2 Postorder Traversal

Alternatively, we might wish to visit each node only after we visit its children (and their subtrees). For example, this would be necessary if we wish to return all nodes in the tree to free store. We would like to delete the children of a node before deleting the node itself. But to do that requires that the children’s children be deleted first, and so on. This is called a postorder traversal.

Example: Postorder enumeration

The postorder enumeration for the tree of Figure #BinTravExample is D B G E H I F C A.

5.5.3 Inorder Traversal

An inorder traversal first visits the left child (including its entire subtree), then visits the node, and finally visits the right child (including its entire subtree). The binary search tree makes use of this traversal to print all nodes in ascending order of value.

Example: Inorder enumeration

The inorder enumeration for the tree of Figure #BinTravExample is B D A G E C H F I.

5.5.4 Implementation

A traversal routine is naturally written as a recursive function. Its input parameter is a pointer to a node which we will call node. The initial call to the traversal function passes in a pointer to the root node of the tree. The traversal function visits node and its children (if any) in the desired order. For example, a preorder traversal specifies that node be visited before its children. This can easily be implemented as follows.

function preorder(node):
    if node is not null:      // Only continue if this is a tree
        visit(node)           // Visit root node
        preorder(node.left)   // Process all nodes in left subtree
        preorder(node.right)  // Process all nodes in right subtree

Function preorder first checks that the tree is not empty (if it is, then the traversal is done and preorder simply returns). Otherwise, preorder makes a call to visit, which processes the root node (i.e., prints the value or performs whatever computation as required by the application). Function preorder is then called recursively on the left subtree, which will visit all nodes in that subtree. Finally, preorder is called on the right subtree, visiting all nodes in the right subtree. Postorder and inorder traversals are similar. They simply change the order in which the node and its children are visited, as appropriate.

5.5.5 Preorder Traversal Practice

5.5.6 Postorder Traversal Practice

5.5.7 Inorder Traversal Practice

5.5.8 Practice questions: Binary tree traversals

Visiting each element in a tree is known as:

Answer TRUE or FALSE.

If you are given the order of the nodes as visited by a postorder traversal and the order of the nodes as visited by an inorder traversal, do you have enough information to reconstruct the original tree? Assume that the nodes all have unique values.

  • Build yourself a small example tree of about 6 or 7 nodes and see what happens.
  • Consider the example where the root has value A. In the postorder traversal, the left subtree is printed, then the right subtree, then A. In the inorder traversal, the left subtree comes first, then the A, then the right subtree.
  • From this information, we always know the root, the contents of its left subtree, and the contents of its right subtree.
  • We can apply this concept recursively to reconstruct the left subtree and the right subtree.

Answer TRUE or FALSE.

If you are given the order of the nodes as visited by a preorder traversal and the order of the nodes as visited by an inorder traversal, do you have enough information to reconstruct the original tree? Assume that the nodes all have unique values.

  • Build yourself a small example tree of about 6 or 7 nodes and see what happens.
  • Consider the example where the root has value A. In the preorder traversal, that A is printed first. In the inorder traversal, the left subtree comes first, then the A, then the right subtree.
  • From this information, we always know the root, the contents of its left subtree, and the contents of its right subtree.
  • We can apply this concept recursively to reconstruct the left subtree and the right subtree.

Answer TRUE or FALSE.

If you are given the order of the nodes as visited by a preorder traversal and the order of the nodes as visited by a postorder traversal, do you have enough information to reconstruct the original tree? Assume that the nodes all have unique values.

  • Consider this example: The preorder traversal prints ABC, and the postorder traversal prints CBA. Can you determine the original tree from this information?
  • In general, if a node has only one subtree, then the preorder and postorder traversals do not give you enough information to determine which side the subtree goes on.

Answer TRUE or FALSE.

When you print out the nodes of binary tree, the leaf nodes appear in the same relative order for the preorder, inorder, and postorder traversals.

  • Take a small binary tree with three or four leaf nodes and see what happens with the traversals.
  • Since all 3 traversals print the left subtree before the right subtree, the leaves have to get printed in the same order.

The nn nodes in a binary tree can be visited in:

  • This would be done by a traversal. How much work does a traversal do at each node?
  • Each node is visted once, with constant time spent at each.

Why does function preorder2() presented in the Traversal module make only half as many recursive calls as function preorder()?

  • All nodes will eventually get called
  • The number of nodes in the tree does not change based on the algorithm used to traverse it.
  • The Full Binary Tree Theorem tells us that roughly half of all pointers in a binary tree are null. No recursive call is made for these pointers by preorder2.