In this article, we shall look into how we can perform a Binary Tree Traversal using different methods.

A Binary Tree is a data structure where every node has at most two children. We call the topmost node as the **Root** node.

Since it could have two children, we could move across the Binary Tree in different ways. Here, we will discuss the three most commonly used methods for traversal, namely:

**PreOrder**Traversal**InOrder**Traversal**PostOrder**Traversal

Let us consider the below Binary Tree and try to traverse it using the above methods.

Table of Contents

## 1. Binary Tree PreOrder Traversal

In a **PreOrder** traversal, the nodes are traversed according to the following sequence from any given node:

- It will mark the current node as visited first.
- Then, if a left child exists, it will go to the left sub-tree and continue the same process.
- After visiting the left sub-tree, it will then move to its right sub-tree and continue the same process.

Since the sequence is node -> left -> right, it is referred to as a * PreOrder traversal*, since the node is visited before the left sub-tree.

Let’s write the C/C++ code for this:

void preorder_traversal(Node* root) { if (root == NULL) return; printf("%d -> ", root->value); preorder_traversal(root->left); preorder_traversal(root->right); }

**PreOrder Traversal for our Binary Tree:**

**10 -> 20 -> 40 -> 50 -> 30 -> 60 -> 70**

## 2. Binary Tree InOrder Traversal

In an **InOrder** traversal, the nodes are traversed according to the following sequence from any given node:

- If a left child exists, it will always go to it first.
- After it visits the left sub-tree, it will visit the currently given node
- After visiting the node, it will then move to its right sub-tree.

As the sequence is left -> node -> right, it will refer to it as an * InOrder traversal*, since we will visit the nodes “in order”, from left to the right.

The C/C++ code is given below

void inorder_traversal(Node* root) { if (root == NULL) return; inorder_traversal(root->left); printf("%d\n", root->value); inorder_traversal(root->right); }

**InOrder Traversal for our Binary Tree:**

**40 -> 20 -> 50 -> 10 -> 60 -> 30 -> 70**

## 3. Binary Tree PostOrder Traversal

In a **PostOrder** traversal, the nodes are traversed according to the following sequence from any given node:

- If a left child exists, it will always go to it first.
- After visiting the left sub-tree, it will then move to its right sub-tree.
- After it visits the right sub-tree, it will finally visit the currently given node

Since the sequence is left -> right -> node, it is referred to as a * PostOrder traversal*, since the nodes are visited at the last.

The C/C++ code is given below

void postorder_traversal(Node* root) { if (root == NULL) return; postorder_traversal(root->left); postorder_traversal(root->right); printf("%d\n", root->value); }

**PostOrder Traversal for our Binary Tree:**

**40 -> 50 -> 20 -> 60 -> 70 -> 30 -> 10**

## 4. Complete Implementation of Binary Tree Traversal in C/C++

To put it all together, I have put together the C/C++ code for all three traversals.

/** Code for https://journaldev.com article Purpose: Performs common Traversals on a Binary Tree @author: Vijay Ramachandran @date: 28-01-2020 */ #include <stdio.h> #include <stdlib.h> // Define the types of Traversals here enum Traversal {PREORDER, INORDER, POSTORDER}; typedef enum Traversal Traversal; typedef struct Node Node; // Define the Tree Node here struct Node { int value; // Pointers to the left and right children Node* left, *right; }; Node* init_tree(int data) { // Creates the tree and returns the // root node Node* root = (Node*) malloc (sizeof(Node)); root->left = root->right = NULL; root->value = data; return root; } Node* create_node(int data) { // Creates a new node Node* node = (Node*) malloc (sizeof(Node)); node->value = data; node->left = node->right = NULL; return node; } void free_tree(Node* root) { // Deallocates memory corresponding // to every node in the tree. Node* temp = root; if (!temp) return; free_tree(temp->left); free_tree(temp->right); if (!temp->left && !temp->right) { free(temp); return; } } void print_tree(Traversal traversal, Node* root) { // Prints the tree according to // various types of traversals if (!root) return; switch(traversal) { case (PREORDER): // Do a Preorder Traversal printf("%d -> ", root->value); print_tree(traversal, root->left); print_tree(traversal, root->right); break; case (INORDER): // Do an Inorder Traversal print_tree(traversal, root->left); printf("%d -> ", root->value); print_tree(traversal, root->right); break; case (POSTORDER): // Do a postorder Traversal print_tree(traversal, root->left); print_tree(traversal, root->right); printf("%d -> ", root->value); break; } } int main() { // Program to demonstrate finding the height of a Binary Tree // Create the root node having a value of 10 Node* root = init_tree(10); // Insert nodes onto the tree root->left = create_node(20); root->right = create_node(30); root->left->left = create_node(40); root->left->right = create_node(50); root->right->left = create_node(60); root->right->right = create_node(70); printf("----Preorder Traversal:----\n"); print_tree(PREORDER, root); printf("\n\n"); printf("----Inorder Traversal:----\n"); print_tree(INORDER, root); printf("\n\n"); printf("----Postorder Traversal:----\n"); print_tree(POSTORDER, root); printf("\n\n"); // Free the tree! free_tree(root); return 0; }

**Output**

----Preorder Traversal:---- 10 -> 20 -> 40 -> 50 -> 30 -> 60 -> 70 -> ----Inorder Traversal:---- 40 -> 20 -> 50 -> 10 -> 60 -> 30 -> 70 -> ----Postorder Traversal:---- 40 -> 50 -> 20 -> 60 -> 70 -> 30 -> 10 ->