1. To traverse a binary tree means to visit each node of the tree exactly once in a systematic fashion.

2. Binary tree is non-linear data structure. Hence, we can’t traverse it like a linked list is a sequential manner but it requires a different approach.

3. We mainly have three algorithms for traversing binary tree. A. Pre-order Traversal

   B. In-order Traversal

   C. Post-order Traversal

4. Consider the Tree

1. Pre-order traversal:-To traverse a non-empty binary tree by pre-order method, the following operations are performed recursively until all nodes are visited: i. Visit the root node. ii. Traverse the left sub-tree fully. iii. Traverse the right sub-tree.

   The pre-order traversal of above tree is A,Q,W,Z,C,H,G,D

        void printPreorder(struct Node* node) 
           { 
               if (node == NULL) 
                   return; 
   
               /* first print data of node */
               cout << node->data << " "; 
   
               /* then recur on left sutree */
               printPreorder(node->left);  
   
               /* now recur on right subtree */
               printPreorder(node->right); 
           }
   

2. In-order Traversal:- To traverse a non-empty binary tree by in-order method, the following operations are performed recursively until all nodes are visited:

i. Traverse the left sub-tree.

ii. Now, visit the root node.

iii. Then, finally traverse the right sub-tree.

The in-order traversal of the tree is Q, Z, W, C, A, H, D, G

void printInorder(struct Node* node) 
        { 
            if (node == NULL) 
                return; 

            /* first recur on left child */
            printInorder(node->left); 

            /* then print the data of node */
            cout << node->data << " "; 

            /* now recur on right child */
            printInorder(node->right); 
        }

1. Post-Order traversal:- To traverse a non-empty binary tree by post-order method, the following operations are performed recursively until all nodes are visited:

i. Traverse the left sub-tree.

ii. Now, move to the right sub tree

iii. Then, finally visit the root node.

The post-order traversal of the tree is Z, C, W, Q, D, G, H, A

void printPostorder(struct Node* node) 
        { 
            if (node == NULL) 
                return; 

            // first recur on left subtree 
            printPostorder(node->left); 

            // then recur on right subtree 
            printPostorder(node->right); 

            // now deal with the node 
            cout << node->data << " "; 
        }