Jump to content

Pre-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 08:57, 8 April 2003 (added a bit more detail.). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In Computer science, Pre-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.

Pre-Order Traversal is a type of Tree Traversal algorithm. Pre order refers to when the root is processed previous to its two subtrees.


Steps to Preorder Traversal

Given a non-empty tree,

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

Given a binary tree PY:

File:TreePY.gif

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

Compare: Inorder traversal, Post-order traversal

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