Tree Traversal

Well I have 4 different types of tree traversals that come to my mind when i think about it :

1. InOrder
2. PreOrder
3. PostOrder
4. Vertical Order Traversal
5. Level Order Traversal [Covered in Some other Lesson]

Inorder Traversal

Algorithm Inorder(tree)
   1. Traverse the left subtree, i.e., call Inorder(left-subtree)
   2. Visit the root.
   3. Traverse the right subtree, i.e., call Inorder(right-subtree)

My Java Based Implementation for it

INORDER TRAVERSAL

PostOrder Traversal

Algorithm Postorder(tree)
   1. Traverse the left subtree, i.e., call Postorder(left-subtree)
   2. Traverse the right subtree, i.e., call Postorder(right-subtree)
   3. Visit the root.

My Java Based Implementation for it

POST ORDER TRAVERSAL

PreOrder Traversal

Algorithm Preorder(tree)
   1. Visit the root.
   2. Traverse the left subtree, i.e., call Preorder(left-subtree)
   3. Traverse the right subtree, i.e., call Preorder(right-subtree)

My Java Based Implementation for it

PREORDER TRAVE

Vertical Order Traversal

Understanding Vertical Order

So the trick in vertical order is to understand the notion of horizontal distance . All items with same horizontal distance should be printed in a vertical fashion

Vertical Order Traversal