Binary Search Tree Implementation IN C++, C, Python and Java

 Binary Search Tree Implementation Part-2

Binary Tree Traversal:

• Tree Traversal is the process of visiting each node in the tree exactly once in some order.
• Based on the order in which the nodes are visited tree traversal algorithms can broadly be classified into two categories. 
• They are : 

1. Breadth - First Traversal
2. Depth - First Traversal

 

1. Breadth - First Traversal:

   •  In breadth first traversal, all the nodes at same level will be visited first, before visiting the nodes at next level.
   • This strategy is called Level - Order 
    

2. Depth First Traversal:

   • In depth first traversal, if we had visited a child node, we will have to visit the whole sub tree of the child before going to the next child.
   • The relative way of visiting the root node, left sub tree, right sub tree can be different.
   • There are three popular strategies in Depth First Traversal.
   • They are :
   1. Pre Order Traversal : Root -> Left Sub Tree -> Right Sub Tree, First we visit the root node, the the left sub tree and then the right sub tree.
   2. In Order Traversal: Left Sub Tree -> Root Node -> Right Sub Tree.
   3. Post Order Traversal : Left Sub Tree -> Right Sub Tree -> Root Node.

    

    

    

Breadth First Traversal Implementation in C++:

// Breadth First Traversal
// WE will use queue to implement this

void LevelOrderTraversal(BSTNode* root){
    if(root==NULL) return;
    queue<BSTNode*> Q;
    Q.push(root);
    // WE will push all the BST nodes into the queue and access one by one by front and poping
    while(!Q.empty()){
        BSTNode* current = Q.front();    
        cout<<current->data<<" ";
        if(current->left!=NULL) Q.push(current->left);
        if(current->right!=NULL) Q.push(current->right);
        Q.pop();    
        /* Queue structure be like : root , root->left, root->right,
     root->left->left, root->left->right, root->right->left, root->right->right, ..... */
    }
     
     
     // Time Complexity of LevelOrderTraversal funtion is: O(n) in all cases
     // Space Complexity will be O(1) in best case and O(n) in average and worst cases.

}

 

 

 

 

 

Depth First Traversal Implementation In C++:

 

PreOrder Implementation ( Iterative Method ):

void PreOrder(BSTNode* root){
    if(root==NULL) return;
    stack<BSTNode*> S;                 // creating a stack S using stl
    S.push(root);                     
    while(S.empty()== false){
        BSTNode* temp = S.top();
        cout<<temp->data<<" ";
        S.pop();
        if(temp->right) S.push(temp->right);
        if(temp->left) S.push(temp->left);
        
    }
}

 

/* Depth First Traversal Algorithms */
// Time Complexity of these algorithms: O(n)
/* Space Complexity is : O(h) h - height, in worst case: O(n) and in best or average case:  O(log n) */

/* Preorder traversal implementation:  root ->left sub tree -> right sub tree */
void Preorder(BSTNode* root){
    if(root==NULL) return;
    cout<<root->data<<" ";   // root data will be visited first
    Preorder(root->left);    // and then left sub tree
    Preorder(root->right);  // and then right sub tree
}


void Inorder(BSTNode* root){
    if(root==NULL) return;
    Inorder(root->left);    //  left sub tree will be visited first
    cout<<root->data<<" ";   // and then root data will be visited
    Inorder(root->right);  // and then right sub tree
}

void Postorder(BSTNode* root){
    if(root==NULL) return;
    Postorder(root->left);    //  left sub tree will be visited first
    Postorder(root->right);  // and then right sub tree
    cout<<root->data<<" ";   // and then root data will be visited
}

 

Check If A Binary Tree is A Binary Search Tree Or Not:

bool IsSubtreeLesser(BSTNode* root, int data){
    if(root==NULL) return true;
    if(root->data <= data && IsSubtreeLesser(root->left,data) && IsSubtreeLesser(root->right, data)){
        return true;
    }
    else {
        return true;
    }
}


bool IsSubtreeGreater(BSTNode* root, int data){
    if(root == NULL) return true;
    if(root->data>= data && IsSubtreeGreater(root->left,data) && IsSubtreeGreater(root->right, data) ){
        return true;
    }
    else {
        return false;
    }
}

bool IsBinarySearchTree(BSTNode* root){
    if(root == NULL) return true;
    if(IsSubtreeLesser(root->left,root->data) && IsSubtreeGreater(root->right, root->data)
    && IsBinarySearchTree(root->left) && IsBinarySearchTree(root->right)){
        return true;
    }
    else {
        return false;
    }
}

Deleting A Node From Binary Search Tree:

// Deleting a node from binary search tree
Node* Delete(Node* root,int data){
    if(root==NULL) reutrn root;
    else if(data<root->data) root->left = Delete(root->left,data);
    else if(data>root->data) root->right = Delete(root->right,data);
    else {
        if(root->left == NULL && root->right==NULL){
            delete root;
            root=  NULL;
        }
        else if(root->left == NULL){
            Node* temp = root;
            root= root->right;
            delete temp;
        }
        else if(root->right==NULL) {
            Node* temp = root;
            root = root->left;
            delete temp;
        }
        else {
            Node* temp = FindMin(root->right);
            root->data = temp->data;
            root->right= Delete(root->right, temp->data);
        }
    }
    return root;
}