Binary Tree

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#include<iostream>
#include <queue>
using namespace std;

class node {
    public:
        int data;
        node* left;
        node* right;

    node(int d) {
        this -> data=d;
        this -> left = NULL;
        this -> right = NULL;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

node* buildTree(node* root) {
    cout<<"Enter The Data:" <<endl;
    int data;
    cin>>data;
    root = new node(data);

    if(data== -1) {
        return NULL;
    }

    cout << "Enter data for inserting in left of "<<data << endl;
    root->left = buildTree(root->left);
    cout <<" Enter data for inserting in right of "<<data<< endl;
    root -> right = buildTree(root->right);
    return root;

}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

//level order triversal
void levelOrderTraversal(node* root)
{
    queue<node*> q;
    q.push(root);
    q.push(NULL);

    while(!q.empty()) {
        node* temp = q.front();
        
        q.pop();

        if(temp==NULL){
            cout<<endl;
            if(!q.empty()){
                q.push(NULL);
            }
        }

        else{
            cout<< temp -> data << " ";
            if(temp-> left) {
            q.push ( temp-> left);
        }

        if(temp->right){
            q.push ( temp-> right);
        }
        }
        

    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

//inorder traversal
void inorder(node* root)
{
    if(root == NULL){
        return;
    }
    inorder(root->left);
    cout<<root->data<<" ";
    inorder(root->right);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

//preorder traversal
void preorder(node* root)
{
    if(root == NULL){
        return;
    }
    cout<<root->data<<" ";
    preorder(root->left);
    
    preorder(root->right);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

//post traversal
void postorder(node* root)
{
    if(root == NULL){
        return;
    }
    postorder(root->left);
    
    postorder(root->right);
    cout<<root->data<<" ";
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

void buildFromLevelOrder(node* &root){
    queue<node*> q;1 3 5 7 11 17 -1 -1 -1 -1 -1 -1 -1
    cout<<"enter data for root"<<endl;
    int data;
    cin>>data;
    root = new node(data);
    q.push(root);

    while(!q.empty()){
        node* temp = q.front();
        q.pop();

        cout<< " enter left node for: "<<root->data<<endl;
        int leftData;
        cin>>leftData;

        if(leftData != -1){
            temp->left = new node(leftData);
            q.push(temp->left);
        }
        cout<< "enter right node for: "<<root->data<<endl;
        int rightData;
        cin>>rightData;

        if(rightData != -1){
            temp->right = new node(rightData);
            q.push(temp->right);
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

int main() {

    node* root = NULL;

    buildFromLevelOrder(root);
    levelOrderTraversal(root);

// 1 3 5 7 11 17 -1 -1 -1 -1 -1 -1 -1

    root = buildTree(root);
    cout<<"the given tree is:"<<endl; 
// 1 3 7 -1 -1 11 -1 -1 5 17 -1 -1 -1
    levelOrderTraversal(root);


    cout<<"inorder traversal is: ";
    inorder(root);
    cout<<endl;

    cout<<"preorder traversal is: ";
    preorder(root);
    cout<<endl;

    cout<<"postorder traversal is: ";
    postorder(root);
    return 0;

}