Jump to content

Post-order traversal

Edit links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Poor Yorick (talk | contribs) at 09:00, 8 April 2003. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In Computer science, Post-order traversal is used in Data structures, and specifically, Trees and Binary Trees.

Programs that utilize tree strucutres need to process nodes in a tree (represented as circles in below diagram). Nodes contain information about an object. For now, let's assume each node contains a letter.

Post-Order Traversal is a type of Tree Traversal algorithm. Post-order refers to when the root is postponed until its two subtrees are processed.

Steps to Post-order Traversal

Given a non-empty tree,

  1. Process the nodes in the left subtree with a recursive call
  2. Process the nodes in the right subtree with a recursive call
  3. Process the root

Given a binary tree PY:

File:TreePY.gif

The order would go D,G,E,B,C,F,A


Compare: Pre-order traversal, Inorder traversal

Retrieved from "https://en.wikipedia.org/w/index.php?title=Post-order_traversal&oldid=811226"