# Traversal of binary tree

**Traversal of binary tree**: A node is visited only once in the traversal of the binary tree. There are three main types of traversal methods in the binary tree.

- In-order traversal
- Pre-order traversal
- Post-order traversal

**In-order traversal:**

In the in-order traversal method, the left child and left subtree are traversed first, afterward the root tree and then the right children or the right subtree are traversed.

**Algorithm of In-order traversal**

In-order-traversal (tree)Step 1: Start with left sub-tree // call In-order (left subtree) Step 2: Then, root tree Step 3: And then, right sub-tree // call In-order (right subtree)

**Example:** Find the in-order traversal for this tree.

**Solution.**

Step 1: Left sub-tree is 1 ? 4 ? 9

Step 2: Root node is 5

Step 3: Right sub-tree is 5 ? 7 ? 2 ? 6 ? 3

In-order Traversal = 1 ? 4 ? 9 ? 5 ? 5 ? 7 ? 2 ? 6 ? 3

**Pre-order Traversal:**

In the pre-order traversal method, the root node is traversed first, then the left subtree, and then the right subtree is traversed.

**Algorithm of pre-order traversal**

Pre-order-traversal (tree)Step 1: Start with the root node Step 2: Then, the left sub-tree // call Pre-order (left subtree) Step 3: And then, right sub-tree // call Pre-order (right subtree)

**Example:** Find the pre-order traversal for this tree.

**Solution.**

Step 1: Root node is 5

Step 2: Left sub-tree is 4 ? 1 ? 9

Step 3: Right sub-tree is 6 ? 7 ? 5 ? 2 ? 3

Pre-order Traversal = 5 ? 4 ? 1 ? 9 ? 6 ? 7 ? 5 ? 2 ? 3

### Post-order traversal:

In the post-order traversal method, the left child and left subtree are traversed first, then the right subtree is traversed, and then the root node.

**Algorithm of Post-order traversal**

Post-order-traversal (tree)Step 1: Start with left sub-tree // call Post-order (left subtree) Step 2: Then, right sub-tree // call Post-order (right subtree) Step 3: And then, root tree

**Example:** Find the Post-order traversal for this tree.

**Solution.**

Step 1: Left sub-tree is 1 ? 9 ? 4 Step 2: Right sub-tree is 5 ? 2 ? 7 ? 3 ? 6 Step 3: Root node is 5 Post-order Traversal = 1 ? 9 ? 4 ? 5 ? 2 ? 7 ? 3 ? 6 ? 5

### Applications of binary tree

- The binary search tree is used in many search applications.
- Nowadays, a binary Space Partition is used for every 3D game.3.
- The binary tree is used in every high bandwidth router that stores the router table.

### Binary tree program in C language

// Binary Tree in C #include <stdio.h> #include <stdlib.h> struct node { int data; struct node *left; struct node *right; }; struct node *newNode(int data) { struct node *node = (struct node *)malloc(sizeof(struct node)); node->data = data; node->left = NULL; node->right = NULL; return (node); } void traversePreOrder(struct node *t) { if (t != NULL) { printf(" %d", t->data); traversePreOrder(t->left); traversePreOrder(t->right); } } void traverseInOrder(struct node *t) { if (t != NULL) { traverseInOrder(t->left); printf(" %d", t->data); traverseInOrder(t->right); } } void traversePostOrder(struct node *t) { if (t != NULL) { traversePostOrder(t->left); traversePostOrder(t->right); printf(" %d", t->data); } } int main() { struct node *root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); printf("The preorder traversal of the tree is: "); traversePreOrder(root); printf("\nThe inorder traversal of the tree is: "); traverseInOrder(root); printf("\nThe postorder traversal of the tree is: "); traversePostOrder(root); }