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)**.

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.