postorder traversal

(algorithm)

Definition: Process all nodes of a tree by recursively processing all subtrees, then finally processing the root.

Also known as postfix traversal.

Generalization (I am a kind of ...)
tree traversal, depth-first search.

See also in-order traversal, preorder traversal, level-order traversal.

Note: For instance, if the "processing" is just printing, a tree is printed as "(first subtree) (second subtree) ... (last subtree) root." Here is pseudocode for a binary tree:

 postorder(tree)
 begin
     if tree is null, return;

     postorder(tree.left_subtree);
     postorder(tree.right_subtree);
     print(tree.root);
 end 

Author: PEB

More information

animation (Java)

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.

Entry modified 2 November 2007.
HTML page formatted Fri Nov 2 14:19:41 2007.

Cite this as:
Paul E. Black, "postorder traversal", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 2 November 2007. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/postorderTraversal.html