Binary tree traversal: Preorder, Inorder, Post-order, BFS, DFS, Level Order, zig zag order

In order to illustrate the 3 traversals - pre order, in-order and post-order lets take following tree:

Preorder traversal:
To traverse a binary tree in Preorder, following operations are carried-out (i) Visit the root, (ii) Traverse the left subtree, and (iii) Traverse the right subtree.
Therefore, the Preorder traversal of the above tree will outputs:
7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10

Implementing pre-order traversal

preorder(N \*root)  
{  
  if(root)  
  {  
    printf("Value : \[%d\]", root->value);  
    preorder(root->left);  
    preorder(root->right);  
  }  
}

More details here.

Inorder traversal:
Inorder traversal prints the binary tree in increasing order. To traverse a binary tree in Inorder, following operations are carried-out (i) Traverse the left most subtree starting at the left external node, (ii) Visit the root, and (iii) Traverse the right subtree starting at the left external node.
Consider the tree below

Therefore, the Inorder traversal of the above tree will outputs:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Implementing inorder traversal(recursive)

inorder(Node \*root)  
{  
  if(root)  
  {  
    inorder(root->left);  
    printf("Value : \[%d\]", root->value);  
    inorder(root->right);  
  }  
}

More details here.

Postorder traversal:
To traverse a binary tree in Postorder, following operations are carried-out (i) Traverse all the left external nodes starting with the left most subtree which is then followed by bubble-up all the internal nodes, (ii) Traverse the right subtree starting at the left external node which is then followed by bubble-up all the internal nodes, and (iii) Visit the root.

Consider the tree below

Therefore, the Postorder traversal of the above tree will outputs:
0, 2, 4, 6, 5, 3, 1, 8, 10, 9, 7

Implementing post order traversal

postorder(Node \*root)  
{  
  if(root)  
  {  
    postorder(root->left);  
    postorder(root->right);  
    printf("Value : \[%d\]", root->value);  
  }  
}  
  

```More details [**here**](http://k2code.blogspot.in/2013/10/binary-tree-post-order-traversal.html).  
Time complexity of above traversals is O(n).  
  
**BFS-Breadth first search**  
This is same as level order traversal, where we go level by level of the tree.  
  
more details here.  
  
**DFS - Depth first search**  
more details here.  
  
**Level order traversal**  
  
**Zig-zag order traversal**  
  
more details [**here**](http://k2code.blogspot.in/2012/01/convert-binary-tree-to-double-linked.html).

See also