Tree Traversal

Example

In this binary search tree, Preorder traversal sequence: F, B, A, D, C, E, G, I, H Inorder traversal sequence: A, B, C, D, E, F, G, H, I Note that the inorder traversal of this binary search tree yields an ordered list Postorder traversal sequence: A, C, E, D, B, H, I, G, F Level-order traversal sequence: F, B, G, A, D, I, C, E, H

Sample implementations

preorder(node)
 print node.value
 if node.left ≠ null then preorder(node.left)
 if node.right ≠ null then preorder(node.right)

inorder(node)
 if node.left  ≠ null then inorder(node.left)
 print node.value
 if node.right ≠ null then inorder(node.right)

postorder(node)
 if node.left  ≠ null then postorder(node.left)
 if node.right ≠ null then postorder(node.right)
 print node.value

All sample implementations will require stack space proportional to the height of the tree. In a poorly balanced tree, this can be quite considerable.

We can remove the stack requirement by maintaining parent pointers in each node, or by threading the tree. In the case of using threads, this will allow for greatly improved inorder traversal, although retrieving the parent node required for preorder and postorder traversal will be slower than a simple stack based algorithm.