Inorder Traversal

Inorder traveral is defined as follows:

Procedure: Inorder Traversal. Let B{B} be a binary tree. To traverse B{B} in inorder:

  1. Traverse the left subtree inorder.
  2. Visit a node.
  3. Traverse the right subtree inorder.

In pseudocode, the procedure looks like:

fn inorder_traverse(tree):
	inorder_traverse(left_subtree);
	visit(node);
	inorder_traverse(right_subtree);

To illustrate, let's use the following tree:

We start by executing inorder_traverse(left_subtree). This means we start by traversing the left subtree. Here, the left subtree starts at nb.{n_b.} nb{n_b} has no left subtree, so we call visit().

After visit() finishes executing, we call inorder_traverse(right_subtree). But, since nb{n_b} has no right subtree, the call does not execute, and the function call inorder_traverse(left_subtree: a) finishes. This leads us to visit(node(a)).

Once we've visited na,{n_a,} we then call inorder_traverse(right_subtree: n_a). This subtree starts with the node nc.{n_c.} Because nc{n_c} has no left subtree, we call visit(node(c)).

Putting these calls all together, for a binary tree of order 3,{3,} the inorder traversal sequence is:

(nb,na,nc) (n_b, n_a, n_c)

If we had a left-skewed binary tree, the sequence would be (nb,na).{(n_b, n_a).}

For a right-skewed binary tree, the sequence would be (na,nc).{(n_a, n_c).} Since the root na{n_a} has no left subtree, we immediately visit nc,{n_c,} then traverse its right subtree. This results in visiting nc.{n_c.}

Implementation

The inorder traversal algorithm is implemented with the following function:

fn inorder(Node* root) -> void:
	if (root != NULL):
		inorder((*root).left_child);
		print "{(*root).data}";
		inorder((*root).right_child);

Suppose we want to inorder-traverse the following tree, named sequoia.

We begin by making the call inorder((*sequoia).root). Suppose root points to the address F0. This results in the call inorder(F0). Making this call, the first statement is inorder((*root).left_child). This evaluates to inorder(F0.left_child), which evaluates to inorder(F1):

Calling inorder(F1), we then call inorder(F1.left_child), which evaluates to inorder(F3).

The call inorder(F3) results in the call inorder(F3.left_child). Because F3 has no left-child, this evaluates to the call inorder(0). This does not lead to any further calls, so it completes and we go to the next call, print "{F3.data}":

Once the print line finishes executing, we go to the next call, inorder(F3.right_child). Here, F3 has no right-child, so the call evaluates to inorder(0).

This completes the call to inorder(F3), so we go back to the call inorder(F1). The next line is print "{F1.data}", so we print the value 8:

We then proceed to the next line, inorder(F1.right_child). Because F1 has a right-child, this call evaluates to inorder(F4). Inside this call, we make the recursive call inorder(F4.left_child). But F4 has no left-child, so the call evaluates to inorder(0).

We go to the next line, print "{F4.data}", which prints the value 6. This line is followed by inorder(F4.right_child). And once again, because F4 has no right-child, the call evaluates to inorder(0):

This completes the call to inorder(F4), which in turn completes the call to inorder(F1). This brings us back to inorder(F0). We execute the line print "{F0.data}", and proceed to inorder(F0.right_child), repeating the process we've covered. All of the calls together yield the following call trace:

Iterative Approach

Just as we saw with preorder traversal, we can also implement an iterative version of inorder traversal. Recall that with inorder traversal, we want to traverse all of the left-subtrees before visiting the node. Thus, the iterative procedure looks similar to the preorderLoop(), with a few modifications:

fn inorderLoop(Node* root) -> void:
	Stack nodeStack;
	while (root != NULL || !isEmpty(nodeStack)):
		if (root != NULL):
			push(nodeStack, root);
			root = (*root).left_child;
		else:
			root = pop(nodeStack);
			print((*root).data);
			root = (*root).right_child;

Notice that with inorderLoop(), the first arm of the while loop is to traverse the entire left-subtree. Only after we've traversed the entire left-subtree do we enter the second arm. Once we've arrived at the state where there are no left-children, we proceed to the second arm. Here, we pop node stack (binding the return value to root), then print() the relevant data. Thereafter, we change root's assigned value to (*root).right_child.

Notice that, broadly, the changes occur in the same way as preorderLoop(). This isn't all that odd, the only change we've made is moving the print() line elsewhere. With preorderLoop(), we printed the value before moving on to the left-child. With inorderLoop(), we print the value before moving on to the right-child. Moving this print() line does not impact the time complexity of traversing the entire treeβ€”it's still O(n),{O(n),} where n{n} is the number of nodes in the tree.