Traversal in Binary Search Tree

Height of a binary tree:

 

Level Order BFS in Binary Search Tree:

#include<bits/stdc++.h>
#include<queue>
using namespace std;

struct Node
{
    char data;
    Node *left;
    Node *right;
};
//Function to print nodes in a binary tree in level order
void LevelOrder(Node *root)
{
    if(root==NULL)
        return;
    queue<Node*> Q;
    Q.push(root);
    //while there is at least one discovered node
    while(!Q.empty())
    {
        Node* current=Q.front();
        Q.pop();
        cout<<current->data<<" ";
        if(current->left!=NULL)
            Q.push(current->left);
        if(current->right!=NULL)
            Q.push(current->right);
    }
}
//Function to insert node in a binary search tree
Node* Insert(Node *root, char data)
{
    if(root==NULL)
    {
        root=new Node();
        root->data=data;
        root->left=root->right=NULL;
    }
    else if(data<=root->data)
        root->left=Insert(root->left,data);
    else
        root->right=Insert(root->right,data);
    return root;
}
int main()
{

    //creating an example tree

    Node *root=NULL;
    root=Insert(root,'M');
    root=Insert(root,'B');
    root=Insert(root,'Q');
    root=Insert(root,'Z');
    root=Insert(root,'A');
    root=Insert(root,'C');
    LevelOrder(root);
}

output:

M B Q A C Z


DFS in Preorder, Inorder, Postorder:

#include<bits/stdc++.h>
#include<queue>
using namespace std;

struct Node
{
    char data;
    Node *left;
    Node *right;
};
//Function to print nodes in a binary tree in level order
void Preorder(struct Node* root){

    if(root==NULL)
        return;
    printf("%c ",root->data);//print data
    Preorder(root->left); //visit left subtree
    Preorder(root->right); //Visit right subtree
}

//function to visit nodes in Inorder
void Inorder(Node* root)
{
    if(root==NULL)
        return;
    Inorder(root->left); //Visit left subtree
    printf("%c ",root->data); //Print  data
    Inorder(root->right); //Visit right subtree
}

void Postorder(Node* root)
{
    if(root==NULL)
        return;
    Postorder(root->left); //visit left subtree
    Postorder(root->right); //visit right subtree
    printf("%c ",root->data); //print data


}


//Function to insert node in a binary search tree
Node* Insert(Node *root, char data)
{
    if(root==NULL)
    {
        root=new Node();
        root->data=data;
        root->left=root->right=NULL;
    }
    else if(data<=root->data)
        root->left=Insert(root->left,data);
    else
        root->right=Insert(root->right,data);
    return root;
}
int main()
{

    //creating an example tree

    Node *root=NULL;
    root=Insert(root,'M');
    root=Insert(root,'B');
    root=Insert(root,'Q');
    root=Insert(root,'Z');
    root=Insert(root,'A');
    root=Insert(root,'C');

    //Print nodes in preorder
    cout<<"Preorder: ";
    Preorder(root);
    cout<<endl;
    //Print nodes in in inorder
    cout<<"Inorder:  ";
    Inorder(root);
    cout<<endl;
    //Print Nodes in postorder
    cout<<"Postorder: ";
    Postorder(root);
    cout<<endl;
    return 0;
}

output:

Preorder: M B A C Q Z
Inorder:  A B C M Q Z
Postorder: A C B Z Q M

 

 

It would be a great help, if you support by sharing :)
Author: zakilive

Leave a Reply

Your email address will not be published.