Jump to content

Inorder traversal

Add links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Poor Yorick (talk | contribs) at 08:58, 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, Inorder 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. The arrows indicate a link between nodes.

InOrder Traversal is a type of Tree Traversal algorithm. Inorder refers to when the root is processed inbetween to its two subtrees.

Steps to Inorder Traversal

Given a non-empty tree,

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

Given a binary tree PY:

File:TreePY.gif

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


Compare: Pre-order traversal, post-order traversal

Retrieved from "https://en.wikipedia.org/w/index.php?title=Inorder_traversal&oldid=811211"