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;
}
Related leetcode problem: https://leetcode.com/problems/binary-tree-level-order-traversal/