Tree Traversal

Binary Tree Traversal

   A binary tree can be traversed in three ways.

            1.  Preorder Traversal (root, left, right)

            2.  Inorder Traversal (left, root, right)

            3.  Postorder Traversal (left, right root)

Preorder Traversal

          Here the traversal is done recursively in the following Manner

1.      Process Root Node

2.      Traverse left subtree in Preorder

3.      Traverse right subtree in preorder

Inorder Traversal

          Here the traversal is done recursively in the following Manner

1.      Traverse left subtree in Inorder

2.      Process Root Node

3.      Traverse right subtree in Inorder

Postorder Traversal

          Here the traversal is done recursively in the following Manner

1.      Traverse left subtree in Postorder

2.      Traverse right subtree in Postorder

3.      Process Root Node

Ex1:

Preorder Traversal:  Formula (Root, Left, Right)

            + * / A ** B C D + E F

Inorder Traversal: Formula (Left, Root, Right)

            A / B **  C * D + E + F

Postorder Traversal: Formula(Left, Right, Root)

            A B C ** / D * E F + +

Ex2:

Preorder Traversal:  Formula (Root, Left, Right)

            A B D K L M E H C F I N G

Inorder Traversal: Formula (Left, Root, Right)

            K L M D B H E A F  N I C G

Postorder Traversal: Formula(Left, Right, Root)

            M L K D H E B N I F G C A