Binary Tree Traversal

Binary Tree Traversal is a process of visiting every node of the tree and print the node value. Unlike linear data structure like arrays and linked lists which can be traversed only in linear manner. Trees can be traversed in multiple manner.

Tree Traversal
Binary Tree Traversal

Majorly, the trees can be traversed in following three manners:

Preorder Traversal: 

The Preorder traversal uses following traversal algorithm to traverse the tree.

  • Visit the Root.
  • Visit the Left Subtree.
  • Visit the Right Subtree.

Application of Preorder Traversal:

  • Preorder traversal is used to create copy of the tree.
  • Preorder traversal is also used to generate prefix expression of an expression tree.

Inorder Traversal:

The Inorder Traversal uses following traversal algorithm to traverse the tree.

  • Visit the Left Subtree.
  • Visit the Root.
  • Visit the Right Subtree.

Application of Inorder Traversal:

  • Inorder tree traversal can be used to check whether tree is binary search tree or not.
  • Inorder tree traversal is used to generate infix expression of expression tree.

Postorder Traversal:

The Postorder Traversal uses following traversal algorithm to traverse the tree.

  • Visit the Left Subtree.
  • Visit the Right Subtree.
  • Visit the Root.

Application of Postorder Traversal:

  • Postorder tree traversal is used to delete the tree. Here, leaves are deleted then respective roots.
  • Postfix Traversal is also used to generate Postfix expression of expression tree.

Implementation of Tree Traversals:

Tree Traversals can be implemented in 3-manners:

  1. Using Recursion.
  2. Using Stack Data Structure.
  3. Using Morris Algorithm.

Here, in this post, we will implement the preorder, inorder and postorder tree traversals using recursion.

C++ Program to Implement Binary Tree Traversal is as follows:

/* C++ Program to Implement Binary Tree Traversal */
#include<bits/stdc++.h>
using namespace std;

typedef struct Node
{
    int data;
    struct Node *left;
    struct Node *right;
    Node(int ele)
    {
        data = ele;
        left = NULL;
        right = NULL;
    }
} Node;

/* Function to Implement Preorder Traversal */
void preorder(Node *root)
{
    if(root == NULL)
    return;
    
    cout<<root->data<<" ";
    
    preorder(root -> left);
    
    preorder(root -> right);
}


/* Function to Implement Inorder Traversal */
void inorder(Node *root)
{
    if(root == NULL)
    return;
    
    inorder(root -> left);
    
    cout<<root->data<<" ";
    
    inorder(root -> right);
}

/* Function to Implement Postorder Traversal */
void postorder(Node *root)
{
    if(root == NULL)
    return;
    
    postorder(root -> left);
    
    postorder(root -> right);
    
    cout<<root->data<<" ";
}
int main()
{
    /* Creating a Binary tree and inserting some nodes in it */
    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);
    root -> right -> left = new Node(6);
    root -> right -> right = new Node (7);
    
    /* Traversing Tree in Preorder, Inorder and Postorder Form */
    
    /* Preorder Traversal */
    cout<<"The Preorder Traversal is:\n";
    preorder(root);
    cout<<endl;
    
    /* Inorder Traversal */
    cout<<"The Inorder Traversal is:\n";
    inorder(root);
    cout<<endl;
    
    /* Postorder Traversal */
    cout<<"The Postorder Traversal is:\n";
    postorder(root);
    cout<<endl;
}

OUTPUT:

The Preorder Traversal is:
1 2 4 5 3 6 7 
The Inorder Traversal is:
4 2 5 1 6 3 7 
The Postorder Traversal is:
4 5 2 6 7 3 1

Related Posts:

  1. Introduction to Tree Data Structure
  2. Print All Leaf Nodes of a Binary Tree
  3. Count Number of Nodes in a Binary Tree
  4. Print Alternate Levels of Binary Tree
  5. Maximum Width of Binary Tree
  6. Level Order Tree Traversal
  7. Left View of Binary Tree
  8. Right View of Binary Tree
  9. Compute Height of Binary Tree
  10. Inorder Tree Traversal Using Stack
  11. Preorder Tree Trasversal Using Stack
  12. Postorder Tree Traversal Using Stack
  13. Vertical Order Tree Traversal
  14. Top View of Binary Tree
  15. Bottom View of Binary Tree
  16. Delete Complete Binary Tree
  17. Check if two trees are mirror Trees of Each Other
  18. Convert Binary Tree to its Mirror Tree
  19. Check if Binary Tree is Symmetric or Not
  20. Print All Root to Leaf Paths in a Binary Tree

You may also like...