Tree Traversals

By | August 17, 2015

There are two kinds of traversal, Breadth First and Depth First.
In this post we will be discussing Depth First Traversals.

They are of 3 types:

1. Preorder
2. Inorder
3. Postorder

PreOrder Tree Traversal

1. If root is NULL then return.
2. Print the root node.
3. Call the recursion on left child of root.
4. Call the recursion on right child of root.

Example

Pre-order: F, B, A, D, C, E, G, I, H

InOrder Tree Traversal

1. If root is NULL then return.
2. Call the recursion on left child of root.
3. Print the root node.
4. Call the recursion on right child of root.

Example

In-order: A, B, C, D, E, F, G, H, I

PostOrder Tree Traversal

1. If root is NULL then return.
2. Call the recursion on left child of root.
3. Call the recursion on right child of root.
4. Print the root node.

Example

Post-order: A, C, E, D, B, H, I, G, F

Here is the C++ Implementation of the same for Integer nodes for the given tree is :

```#include <bits/stdc++.h>
using namespace std;

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

node * newNode(int a)
{
node *x=new node;
x->data=a;
x->left=NULL;
x->right=NULL;
return x;
}

void Inorder(node * root)
{
if(!root)
return;
Inorder(root->left);
cout<<root->data<<" ";
Inorder(root->right);
}

void Preorder(node * root)
{
if(!root)
return;
cout<<root->data<<" ";
Preorder(root->left);
Preorder(root->right);
}

void Postorder(node * root)
{
if(!root)
return;
Postorder(root->left);
Postorder(root->right);
cout<<root->data<<" ";
}

int main() {
node *root        = newNode(1);
root->left        = newNode(2);
root->right       = newNode(3);
root->left->left  = newNode(4);
root->left->right = newNode(5);

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

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

cout<<"\nPostorder traversal of binary tree is \n";
Postorder(root);
return 0;
}```

Time Complexity: O(n) // as all the nodes are visited once, where n is the number of nodes in the tree

Output:

```Preorder traversal of binary tree is
1 2 4 5 3
Inorder traversal of binary tree is
4 2 5 1 3
Postorder traversal of binary tree is
4 5 2 3 1```