Best Data Structures and Algorithm Course Get now!

# Binary Tree Traversal in C++

It is the process of visiting all the nodes of the binary tree. There are three ways for tree traversal that are Pre-order, In-order, and post-order.
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.
Pre-order In-order Post-order
Process the root R. Traverse the left subtree of R in preorder. Traverse the left sub tree of R in postorder.
Traverse the left subtree of R in preorder. Process the root R. Traverse the right subtree of R inorder.
Traverse the right subtree of R in preorder Traverse the right subtree of R inorder. Process the root R.

## C++ Program for Binary Tree Traversal in data structure

```#include<iostream>
#include<stack>
#include<queue>

using namespace std;

class Node{
public:
Node* lchild;
int data;
Node* rchild;
Node() {};
Node(int data);
};

Node::Node(int data) {
lchild = nullptr;
this->data = data;
rchild = nullptr;
}

class Tree{
private:
Node* root;
public:
Tree();
void CreateTree();
void Preorder(Node* p);
void Preorder() { Preorder(root); }  // Passing Private Parameter in Constructor
void Inorder(Node* p);
void Inorder() { Inorder(root); }
void Postorder(Node* p);
void Postorder() { Postorder(root); }
void Levelorder(Node* p);
void Levelorder() { Levelorder(root); }
int Height(Node* p);
int Height() { return Height(root); }
void iterativePreorder(Node* p);
void iterativePreorder() { iterativePreorder(root); }
void iterativeInorder(Node* p);
void iterativeInorder() { iterativeInorder(root); }
void iterativePostorder(Node* p);
void iterativePostorder() { iterativePostorder(root); }
Node* generateFromTraversal(int inorder[], int preorder[], int inStart, int inEnd);
};

Tree::Tree() {
root = nullptr;
}

void Tree::CreateTree() {
Node* p;
Node* t;
int x;
queue<Node*> q;

root = new Node;
cout << "Enter root data: " << flush;
cin >> x;
root->data = x;
root->lchild = nullptr;
root->rchild = nullptr;
q.emplace(root);

while (! q.empty()){
p = q.front();
q.pop();

cout << "Enter left child data of " << p->data << ": " << flush;
cin >> x;
if (x != -1){
t = new Node;
t->data = x;
t->lchild = nullptr;
t->rchild = nullptr;
p->lchild = t;
q.emplace(t);
}

cout << "Enter right child data of " << p->data << ": " << flush;
cin >> x;
if (x != -1){
t = new Node;
t->data = x;
t->lchild = nullptr;
t->rchild = nullptr;
p->rchild = t;
q.emplace(t);
}
}
}

```

## Binary tree traversal iterative

Preorder Traversal:
```void Tree::iterativePreorder(Node *p) {
stack<Node*> stk;
while (p != nullptr || ! stk.empty()){
if (p != nullptr){
cout << p->data << ", " << flush;
stk.push(p);
p = p->lchild;
} else {
p = stk.top();
stk.pop();
p = p->rchild;
}
}
cout << endl;
}
```
Inorder Traversal:
```void Tree::iterativeInorder(Node *p) {
stack<Node*> stk;
while (p != nullptr || ! stk.empty()){
if (p != nullptr){
stk.push(p);
p = p->lchild;
} else {
p = stk.top();
stk.pop();
cout << p->data << ", " << flush;
p = p->rchild;
}
}
cout << endl;
}
```
Postorder Traversal:
```void Tree::iterativePostorder(Node *p) {
stack stk;
long int temp;
while (p != nullptr || ! stk.empty()){
if (p != nullptr){
stk.push((long int)p);
p = p->lchild;
} else {
temp = stk.top();
stk.pop();
if (temp > 0){
stk.push(-temp);
p = ((Node*)temp)->rchild;
} else {
cout << ((Node*)(-1 * temp))->data << ", " << flush;
p = nullptr;
}
}
}
cout << endl;
}
```

## Recursive Binary tree traversal

```void Tree::Preorder(Node *p) {
if (p){
cout << p->data << ", " << flush;
Preorder(p->lchild);
Preorder(p->rchild);
}
}

void Tree::Inorder(Node *p) {
if (p){
Inorder(p->lchild);
cout << p->data << ", " << flush;
Inorder(p->rchild);
}
}

void Tree::Postorder(Node *p) {
if (p){
Postorder(p->lchild);
Postorder(p->rchild);
cout << p->data << ", " << flush;
}
}
```

## Level order traversal

In this program, we will learn print level order traversal of a tree.
```void Tree::Levelorder(Node *p) {
queue<Node*> q;
cout << p->data << ", " << flush;
q.push(p);

while (! q.empty()){
p = q.front();
q.pop();

if (p->lchild){
cout << p->lchild->data << ", " << flush;
q.push(p->lchild);
}

if (p->rchild){
cout << p->rchild->data << ", " << flush;
q.push(p->rchild);
}
}
}

```

## Reverse Level Order Traversal

```vector<int> reverseLevelOrder(Node *p)
{

vector<int> ans;
if(!p)
return ans;
queue<Node *> q;
q.push(p);
Node * temp;
while(!q.empty())
{
temp=q.front();
q.pop();
if(temp->right)
q.push(temp->right);
if(temp->left)
q.push(temp->left);

ans.push_back(temp->data);
}
reverse(ans.begin(),ans.end());
return ans;
}
```

## Binary Tree Zigzag Level Order Traversal

```vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
if(!root)
return {};
vector<vector<int>> ans;
vector<int> v;
int count=0;
TreeNode* p;
queue<TreeNode * > q;
q.push(root);
int size=0;
while(!q.empty())
{
v.clear();
count++;
size=q.size();

for(int i=0;i<size;i++)
{
p=q.front();
q.pop();
if(p->left)
q.push(p->left);
if(p->right)
q.push(p->right);
v.push_back(p->val);

}
if(count%2==0)
{
reverse(v.begin(),v.end());
}
ans.push_back(v);
}
return ans;
}
```

## Vertical Traversal of Binary Tree

```vector<int> verticalOrder(Node *root)
{
queue<pair<Node *,int>> q;
vector<int> v;
vector<vector<int>> ans;
map<int,vector<int>> mp;
q.push(make_pair(root,0));
while(!q.empty())
{
pair<Node *,int> p=q.front();
q.pop();
Node  * temp=p.first;
int pos=p.second;
if(temp->left)
q.push(make_pair(temp->left,pos-1));
if(temp->right)
q.push(make_pair(temp->right,pos+1));
mp[pos].push_back(temp->data);

}
for(auto &pr:mp)
{
for(int i=0;i<pr.second.size();i++)
{
v.push_back(pr.second[i]);
}

}
return v;
}
```