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

Here we follow this approach

  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

PreOrder Traversal

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

InOrder Tree Traversal

Here we follow this approach

  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

Inorder Traversal

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

PostOrder Tree Traversal

Here we follow this approach

  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

Postorder Traversal

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 :

Binary Tree

#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