Binary Tree Traversals

The process of visiting all nodes of a tree is called tree traversal.

The current node (referred to as “visiting” the node and denoted with “D”), traversing to the left child node (denoted with “L”), and traversing to the right child node (denoted with “R”).

There are 6 possibilities:

1. LDR : Process left subtree, process the current node data and then process right subtree
2. LRD
3. DLR
4. DRL
5. RDL
6. RLD

Classifying the Traversals

The classification is based on the order in which current node is processed. That means, if we are classifying based on current node (D) and if D comes in the middle then it does not matter whether L is on left side of D or R is on left side of D.

total 6 possibilities are reduced to 3 and these are:

• Preorder (DLR) Traversal : 1 2 4 5 3 6 7
• Inorder (LDR) Traversal : 4 2 5 1 6 3 7
• Postorder (LRD) Traversal : 4 5 2 6 7 3 1

There is another traversal method which does not depend on the above orders and it is: 

Level Order Traversal: This method is inspired from Breadth First Traversal (BFS of Graph algorithms).