Tree Traversal - Inorder Preorder Postorder C++ Program

Table of contents

What is Tree Traversal

Tree Traversal is the method in which each node in the tree is visited exactly once in a systematic manner. So to access each node of a tree there are 3 traversal methods such as Inorder, PreOrder, and PostOrder.

For instance, you might want to find the sum of all values in the tree or find the largest and smallest value in a tree. For all these operations, you will need to visit each node of the tree.

Basic Tree Structure

The basic building block of a tree is the Structure, so define a basic structure as a node.

You need to assign a basic data type like int to store the value. Also declare two pointers as *Left and *Right which are the links to the child nodes or links to the left and right subtrees.

struct node {
int data;
struct node* left;
struct node* right;
}

The struct node pointed to by left and right might have other left and right children so we should always think of them as sub-trees instead of sub-nodes.

According to this structure, always consider every tree as a combination of a node carrying data and has left and right sub trees.

Types of Tree Traversal

In Order
Pre Order
Post Order

Linear data structures such as Arrays, Linked Lists, Queues, and Stacks have only one pre-determined way to read the data.

But a hierarchical data structure like Trees and graphs can be traversed or visited in different ways.

In order traversal

Inorder Traversal is one the most used type of DFS (Depth First Search) Traversal of the tree.

First, visit all the nodes in the Left sub tree
Then visit the Root Node
Visit all the nodes in the Right sub tree

inorder(root->left)
display(root->data)
inorder(root->right)Code language: PHP (php)

Pre order traversal

First, Visit the Root Node.
Then, Visit all the nodes in the Left sub tree
Visit all the nodes in the Right sub tree

display(root->data)
preorder(root->left)
preorder(root->right)Code language: PHP (php)

Post order traversal

First, Visit all the nodes in the Left sub tree
Visit all the nodes in the Right sub tree
At Last, Visit the Root Node

postorder(root->left)
postorder(root->right)
display(root->data)Code language: PHP (php)

C++ Program Tree Traversal

// C++ program tree traversals
#include <iostream>
using namespace std;

struct Node {
	int data;
	struct Node *left, *right;
	Node(int data)
	{
		this->data = data;
		left = right = NULL;
	}
};

/* postorder traversal. */

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 << " ";
}

/* inorder*/

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);
}

/* preorder*/

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);
}

int main()
{
	struct Node* root = new Node(1);
	root->left = new Node(2);
	root->right = new Node(3);
	root->left->left = new Node(4);
	root->left->right = new Node(5);

	cout << "\nPreorder traversal of binary tree is \n";
	printPreorder(root);

	cout << "\nInorder traversal of binary tree is \n";
	printInorder(root);

	cout << "\nPostorder traversal of binary tree is \n";
	printPostorder(root);

	return 0;
}
Code language: PHP (php)