binary tree inorder traversal code example
Example 1: vertical traversal of binary tree
/* This is just a function of vertical traversal of binary tree. You need to
write required code. Thank you. */
// Class to store node and it's distance from parent.
class Obj
{
public:
Node *root;
int dis;
Obj(Node *node, int dist)
{
root = node;
dis = dist;
}
};
// Main logic of vertical traversal.
void verticalTraversal(Node *root)
{
queue<Obj*> q;
Obj *ob = new Obj(root, 0);
q.push(ob);
map<int, vector<int>> m;
while(!q.empty())
{
Obj *ob = q.front();
q.pop();
if(m.find(ob->dis) != m.end())
{
m[ob->dis].push_back(ob->root->data);
}
else
{
vector<int> v;
v.push_back(ob->root->data);
m[ob->dis] = v;
}
if(ob->root->left != NULL)
q.push(new Obj(ob->root->left, ob->dis-1));
if(ob->root->right != NULL)
q.push(new Obj(ob->root->right, ob->dis+1));
}
for(auto it=m.begin(); it!=m.end(); it++)
{
vector<int> v1 = (*it).second;
for(int j = 0; j<v1.size(); j++)
cout << v1[j] << "\t";
}
cout << endl;
}
Example 2: preorder traversal
#include <iostream>
using namespace std;
class node{
public:
int data;
node* left;
node* right;
node(int d){
data = d;
left = NULL;
right = NULL;
}
};
node* buildTree(){
int d;
cin>>d;
if(d==-1){
return NULL; //to attach a NULL pointer[in case of no child] enter -1
}
node * root = new node(d);
root->left = buildTree();
root->right = buildTree();
return root;
}
//REQUIRED FUNCTION: Inorder Traversal
void printIn(node*root){
if(root==NULL){
return;
}
//Otherwise Left Root Right
printIn(root->left);
cout<<root->data<<" ";
printIn(root->right);
}
int main(){
node* root = buildTree();
printIn(root);
return 0;
}
//SAMPLE INPUT TO RUN THE CODE ON ANY ONLINE IDE:
//8 10 1 -1 -1 6 9 -1 -1 7 -1 -1 3 -1 14 13 -1 -1 -1