example:

DFS:
Inorder: (Left, Root, Right), 4 2 5 1 3
Preorder: (Root, Left, Right), 1 2 4 5 3
Postorder:(Left, Right, Root), 4 5 2 3 1

BFS:(level order)
1 2 3 4 5

In-Order Traversal

  • visit left branch, then current node, and finally, the right branch.
  • Left->Root->Right
    1
    2
    3
    4
    5
    6
    7
    void inOrder(TreeNode* root){
      if(!root){
        inOrder(root->left);
        visit(root);
        inOrder(root->right);
      }
    }

Pre-Order Traversal

  • visit current node before its child nodes(hence called pre-order)
  • In a pre-order traversal, the root is always the first node visited.
  • Root->Left->Right
    1
    2
    3
    4
    5
    6
    7
    void PreOrder(TreeNode* root){
      if(!root){
        visit(root);
        inOrder(root->left);
        inOrder(root->right);
      }
    }

Post-Order Traversal

  • visit current node after its child nodes(hence post-order)
  • In a post-order, the root is always the last node visited.
  • Left->Right->Root
    1
    2
    3
    4
    5
    6
    7
    void PostOrder(TreeNode* root){
      if(!root){
        inOrder(root->left);
        inOrder(root->right);
        visit(root);
      }
    }

reference:
https://goo.gl/vCGqY8