Binary Tree traversal in C++

Binary Tree traversal: It is the process of visiting (or printing) all the nodes of the binary tree. There are three ways for tree traversal that are Pre-order, In-order, and Post-order.

Traversing Binary Trees

  • Pre-order
  • In-order
  • Post-order

Preorder:

  • Process the root R.

  • Traverse the left subtree of R in preorder.

  • Traverse the right subtree of R in preorder

Inorder:

  • Traverse the left subtree of R in inorder.
  • Process the root R.
  • Traverse the right subtree of R inorder.

Postorder: 

  • Traverse the left sub tree of R in postorder.
  • Traverse the right sub tree of R in postorder.
  • Process the root R.

Q. Write the Inorder, preorder, and postorder traversal of the following tree:-

 

Binary Tree traversal in C++

Solution:

Inorder:- Left Root Right

              7 5 8 4 10 1

Preorder:- Root Left Right

                  4 5 7 8 10 1

Postorder:- Left Right Root

                   7 8 5 1 10 4

 

Tree Traversal C++ Code

In this program, we are going to perform binary tree traversal in c++ in all three ways that are inorder, preorder, and postorder.

Binary Tree traversal in C++

#include<iostream>
using namespace std;
void preorder(struct node *root);
void inorder(struct node *root);
void postorder(struct node * root);
struct node *create();
struct node
{
    int data;
    struct node *left,*right;
};
int main()
{
    struct node *root;
    root=create();
    cout<<"\n Preorder:";
    preorder(root);
    cout<<"\n Inorder:";
    inorder(root);
    cout<<"\n Postorder:";
    postorder(root);
    return 0;
}
void preorder(struct node *root)
{
    if(root==0)
    return;
    cout<<root->data<<" ";
    preorder(root->left);
    preorder(root->right);
}
void inorder(struct node *root)
{
    if(root==0)
    return;
    else
    {
        inorder(root->left);
    }
    cout<<root->data<<" ";
    inorder(root->right);
}


void postorder(struct node * root)
{
    if(root==0)
    return;
    else
    postorder(root->left);
    postorder(root->right);
    cout<<root->data<<" ";
}
struct node *create()
{
    struct node *newnode;
    newnode=new node();
    int x;
    cout<<"\n Enter Data(-1 for no node):";
    cin>>x;
    if(x==-1)
    return 0;
    newnode->data=x;
    cout<<"\n Enter left child of "<<x;
    newnode->left=create();
    cout<<"\n Enter right child of "<<x;
    newnode->right=create();
    return newnode;
}

Binary tree traversal in c++ program with output


Enter Data(-1 for no node):4 

 Enter left child of 4     

 Enter Data(-1 for no node):5

 

 Enter left child of 5     

 Enter Data(-1 for no node):7

 

 Enter left child of 7

 Enter Data(-1 for no node):-1

 

 Enter right child of 7

 Enter Data(-1 for no node):-1

 

 Enter right child of 5

 Enter Data(-1 for no node):8

 

 Enter left child of 8

 Enter Data(-1 for no node):-1

 

 Enter right child of 8

 Enter Data(-1 for no node):-1

 

 Enter right child of 4

 Enter Data(-1 for no node):10

 

 Enter left child of 10

 Enter Data(-1 for no node):-1

 

 Enter right child of 10

 Enter Data(-1 for no node):1

 

 Enter left child of 1

 Enter Data(-1 for no node):-1

 

 Enter right child of 1

 Enter Data(-1 for no node):-1

 

 Preorder:4 5 7 8 10 1

 Inorder:7 5 8 4 10 1

 Postorder:7 8 5 1 10 4

 

Binary tree: Each node can have at most two children.

If you have any doubts, let me know in the comment section.

Related posts:

Menu Driven C++ Program for a Simple Calculator

How to reverse an array in c++



Siddharth Jha
• Software Developer • Website Developer • Masters in SEO • Social Media Manager

Related Posts

Post a Comment

Follow by Email