Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

Postorder Traversal

The second depth-first traversal method we consider is postorder traversal  . In contrast with preorder traversal, which visits the root first, postorder traversal visits the root last. To do a postorder traversal of a general tree:

  1. Do a postorder traversal each of the subtrees of the root one-by-one in the order given; and then
  2. visit the root.
To do a postorder traversal of a binary tree
  1. Traverse the left subtree; and then
  2. traverse the right subtree; and then
  3. visit the root.
A postorder traversal of the tree shown in Figure gif visits the nodes in the following order:

displaymath63848

next up previous contents index

Bruno Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.