C Program To Implement Binary Tree Traversals - In-order, Pre-order and Post-order

Tree traversal is the process of visiting all the nodes in a tree in a specific order.  There are three types of tree traversals.

• Pre-Order Traversal
• Post Order Traversal
• In-order Traversal

Pre-order Traversal:

• Visit the root node.
• Recursively traverse left sub-tree(in pre-order).
• Recursively traverse right sub-tree(in pre-order).

Algorithm for Pre-Order tree traversal:
void preorder(Treenode T) {
          if (T == NULL)
               return;
           printData(T->data);
           preorder(T->left);
           preorder(T->right);
           return;
}


Example:
                                   *
                                /      \
                              +         -
                            /   \      /  \
                           A    B    C   D

Step 1: Visit root node and store the key '*' to output.
Output: *

Step 2: Recursively traverse left subtree of '*'

                        +
                       /  \
                      A   B     Preorder traversal: + A B

Output: * + A B

Step 3: Recursively traverse right subtree of '*'

                         -
                       /  \
                      C   D     Preorder traversal: - C D

Output: * + A B - CD

Preorder:  * + A B - C D

Post Order Traversal:

• Recursively traverse left subtree(in post order).
• Recursively traverse right subtree(in post order).
• Visit the root node.

Algorithm for Post order tree traversal:
void postorder(Treenode T) {
          if (T == NULL)
               return;
           postorder(T->left);
           postorder(T->right);
           printData(T->data);
           return;
}

Example:
                                   *
                                /      \
                              +         -
                            /   \      /  \
                           A    B    C   D

Preorder: A B + C D - *



Inorder Traversal:

• Recursively traverse left subtree(inorder).
• Visit the root node.
• Recursively traverse right subtree(inorder).

Algorithm for Inorder tree traversal:
void inorder(Treenode T) {
          if (T == NULL)
               return;
           inorder(T->left);
           printData(T->data);
           inorder(T->right);
           return;
}



Example:
                                   *
                                /      \
                              +         -
                            /   \      /  \
                           A    B    C   D

Inorder: A + B * C - D

See Also:
C Program To Represent Binary Search Tree Using Arrays
C Program To Perform Insertion, Deletion and Traversal In Binary Search Tree
C Program To Implement Binary Tree Traversals: In-order, Pre-order and Post-order
C Program To Implement Dictionary Using Binary Search Tree
C Program To Perform Searching in Binary Search Tree

C Program To Perform Insertion, Deletion & Traversal In Threaded BST

C Program To Perform Insertion, Deletion And Traversal In Red Black Tree
C Program To Perform Insertion, Deletion and Traversal in AVL Tree
C Program To Perform Insertion, Deletion and Traversal In B-Tree
C Program To Implement Priority Queue Using Binary Heaps
Construct Binary Search Tree From In-order and Pre-order Traversal Outputs

Example Program For Binary Tree Traversals - Post-order, Pre-order, In-order):

---

  #include <stdio.h>
  #include <stdlib.h>

  struct tnode {
        int data;
        struct tnode *left, *right;
  };

  struct tnode *root = NULL;

  /* creating node of the tree  and fill the given data */
  struct tnode * createNode(int data) {
        struct tnode *newNode;
        newNode  = (struct tnode *) malloc(sizeof(struct tnode));
        newNode->data = data;
        newNode->left = NULL;
        newNode->right = NULL;
        return (newNode);
  }

  /* inserting a new node into the tree */
  void insertion(struct tnode **node, int data) {
        if (!*node) {
                *node = createNode(data);
        } else if (data < (*node)->data) {
                insertion(&(*node)->left, data);
        } else if (data > (*node)->data) {
                insertion(&(*node)->right, data);
        }
  }

  /* post order tree traversal */

  void postOrder(struct tnode *node) {

        if (node) {

                postOrder(node->left);

                postOrder(node->right);

                printf("%d  ", node->data);

        }

        return;

  }

  /* pre order tree traversal */

  void preOrder(struct tnode *node) {

        if (node) {

                printf("%d  ", node->data);

                preOrder(node->left);

                preOrder(node->right);

        }

        return;

  }

  /* inorder tree traversal */

  void inOrder(struct tnode *node) {

        if (node) {

                inOrder(node->left);

                printf("%d  ", node->data);

                inOrder(node->right);

        }

        return;

  }

  int main() {

        int data, ch;

        while (1) {

                printf("\n1. Insertion\n2. Pre-order\n");

                printf("3. Post-order\n4. In-order\n");

                printf("5. Exit\nEnter your choice:");

                scanf("%d", &ch);

                switch (ch) {

                        case 1:

                                printf("Enter ur data:");

                                scanf("%d", &data);

                                insertion(&root, data);

                                break;

                        case 2:

                                preOrder(root);

                                break;

                        case 3:

                                postOrder(root);

                                break;

                        case 4:

                                inOrder(root);

                                break;

                        case 5:

                                exit(0);

                        default:

                                printf("U've entered wrong opetion\n");

                                break;

                }

        }

        return 0;

  }

Input Tree:
                                                     20
                                                   /      \
                                                  15     30
                                                /       /   \
                                               8       25   40
                                                             \
                                                 10

  Output: (Binary Tree Traversal - Inorder, Postorder & Preorder)

  jp@jp-VirtualBox:$ ./a.out
  1. Insertion
  2. Pre-order
  3. Post-order
  4. In-order
  5. Exit
  Enter your choice:1
  Enter ur data:20
  1. Insertion
  2. Pre-order
  3. Post-order
  4. In-order
  5. Exit
  Enter your choice:1
  Enter ur data:15
  1. Insertion
  2. Pre-order
  3. Post-order
  4. In-order
  5. Exit
  Enter your choice:1
  Enter ur data:8
  1. Insertion
  2. Pre-order
  3. Post-order
  4. In-order
  5. Exit
  Enter your choice:1
  Enter ur data:10
  1. Insertion
  2. Pre-order
  3. Post-order
  4. In-order
  5. Exit
  Enter your choice:1
  Enter ur data:30
  1. Insertion
  2. Pre-order
  3. Post-order
  4. In-order
  5. Exit
  Enter your choice:1
  Enter ur data:25
  1. Insertion
  2. Pre-order
  3. Post-order
  4. In-order
  5. Exit
  Enter your choice:1
  Enter ur data:40
  1. Insertion
  2. Pre-order
  3. Post-order
  4. In-order
  5. Exit
  Enter your choice:2
  20  15  8  10  30  25  40  
  1. Insertion
  2. Pre-order
  3. Post-order
  4. In-order
  5. Exit
  Enter your choice:3
  10  8  15  25  40  30  20  
  1. Insertion
  2. Pre-order
  3. Post-order
  4. In-order
  5. Exit
  Enter your choice:4
  8  10  15  20  25  30  40  
  1. Insertion
  2. Pre-order
  3. Post-order
  4. In-order
  5. Exit
  Enter your choice:5