Tree Traversals

What is a Tree?

A Data Structure is a way to organize and store data using a Computer Program. We store data in a certain way to suit the needs of the Program that we are writing.

A Tree is a special type of Graph Data Structure where all the nodes originate either directly or indirectly from exactly one node, called the root node.

General Tree Structure

What is a Tree Traversal?

Tree traversal is the process of visiting each node of the tree data structure.

Why do we need to traverse a Tree?

We traverse a Tree in order to find and process the information that is stored in a tree data structure.

What are the different types of Tree Traversals?

Like Graph Traversal there are two basic types of Tree Traversals:
  1. Breadth First Search or Level Order Traversal
  2. Depth First Search
Depth First Search is further divided into three basic traversals. Note, that there can be more but these are the three basic ones.
  1. Preorder Traversal - Root, Left, Right
  2. Inorder Traversal - Left, Root, Right
  3. Postorder Traversal- Left, Right, Root
Algorithm for Preorder Traversal:
  1. Visit Root node.
  2. Visit Left node or Left subtree.
  3. Visit Right node or Right subtree.
Algorithm for Inorder Traversal:
  1. Visit Left node or Left subtree.
  2. Visit Root node.
  3. Visit Right node or Right subtree.
Algorithm for Postorder Traversal:
  1. Visit Left node or Left subtree.
  2. Visit Right node or Right subtree.
  3. Visit Root node.
The youtube tutorial below explains this concept really well: