Implement a Binary tree with inOrder postOrder preOrder

Implement a Binary tree
Spread the love
  •  
  •  
  •  
  •  
  •  
  •  
  •  

 A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. In this binary tree data structure tutorial, I will show you how to implement a binary tree with preOrder, inOrder, and postOrder traversal using C++.

Implement a Binary tree with inOrder postOrder preOrder traversal

Well, The prerequisite of implementation is you have to knowledge about the link lists and recursion. I assume you are familiar with the link list and recursion. The space complexity of the binary search is O(1). The time complexity of the binary search algorithm is O(log n).

Implement a Binary tree
Implement a Binary tree

Well, First you have to define a structure. Look at this below code

Define Structure

typedef struct Node{
    int data;
    Node *left,*right;
}node;

In this structure, I take an integer variable to store our data. Then take node left and right to store our left and right node. Which data type is Node

Implement a Binary tree

Well, now I will write a function that creates a new node and its data type should be our Node type which is I have created before.

Create a Node

node *create_node()
{
    int x;
    node *newNode;
    newNode = new node;
    cout<<"Enter data ( -1 for no node ) : ";
    cin>>x;
    if(x == -1)
    {
        return 0;
    }
    else{
        newNode->data = x;
        cout<<"\nEnter left child of "<<x<<" , ";
        newNode->left = create_node();
        cout<<"\nEnter right child of "<<x<<" , ";
        newNode->right = create_node();
        return newNode;
    }
}

Well, in this create function first I declare an integer variable (x) for checking conditions. Then declare a node pointer variable *newNode. After then in this newNode variable, I have created a new instance of our node ( structure). Then scan this (x) value. Then check a condition if x value is equal to -1 then return 0. That means we don’t have node more. (I am sure you don’t understand this line, don’t worry!)

In this else section, I assigned newNode->data = x . Then print a message for the user to hints at the left node. Then newNode->left = create_node(), I am calling again create_node function in our newNode’s left child. It’s a recursive call and it will go until the user input is -1. (I hope right now you will understand my previous argument).

Well, Then newNode->right = create_node(), I am calling again create_node function in our newNode’s right child. It’s also a recursive call and it will go until the user input is -1.

Well, our create_node function has been done. Now time to call it from the main function. You may notice that the create_node function returns a root node. To store this root note we have to declare a node variable. Look bellow code

int main()
{
node *root;
    root = 0;
    root = create_node();
}

Pre-order Traversal

Well, now we have to write another function which will be Preorder traversal. We know that pre-order traversal first visit root then visit left after then right node. Well, Let’s implement this login in a function.

void preOrder(node *root)
{
    if(root ==0 )
    {
        return ;
    }
       else{
        cout<<" "<<root->data<<" ";
        preOrder(root->left);
        preOrder(root->right);
    }

Well, Our preOrder function has a perimeter, which takes the root node. Inside the function first, we have to check that root is empty or not . If the root is equal to zero then return nothing. Else print the root value. After then call again the preOrder function which argument should be root->left. It will recursively print root value then call again preOrder function argument with root->right.

In-order Traversal

Well, now I will show you how to write inOrder traversal function. In-order traversal first visit left node then visit root and finally visit right node. Let’s see this code

void inOrder(node *root)
{
    if(root == 0)
    {
        return ;
    }
    else{
        inOrder(root->left);
        cout<<" "<<root->data<<" ";
        inOrder(root->right);
    }
}

Post-order traversal

void postOrder(node *root)
{
    if(root==0)
    {
        return;
    }
    else{
        postOrder(root->left);
        postOrder(root->right);
       cout<<" "<<root->data<<" ";
    }
}

Well, Our output will be this (thumbnail) binary tree. Pre-Order : 1 2 4 5 3 7 . In-Order : 4 2 5 1 6 3 7. Post-Order : 4 5 2 6 7 3 1

Github link: https://github.com/AR-Shahin/Data_Structure_and_Algorithm/blob/main/Tree/binary_tree_using_cpp.txt

Hope you will enjoy this tutorial.

Read More : How to implement Queue using Link List?


Spread the love
  •  
  •  
  •  
  •  
  •  
  •  
  •  

About Anisur Rahman Shahin

Hello. My name is Shahin. I'm a tech enthusiast guy. Personally, I’m Optimistic and always in hurry kinda person. I'm a freelance web developer. I am working at Zakir Soft as Laravel Developer. My Portfolio website: https://devshahin.com/

View all posts by Anisur Rahman Shahin →

Leave a Reply

Your email address will not be published. Required fields are marked *