Binary Search Tree Implementation In C++, Python , C, Java | Tree Data Structure | Binary Tree Data structure

•  The tree Data structure is used to store hierarchical data.
• The tree is a non-linear data structure that is a collection of nodes linked together to simulate hierarchy.
• The tree has a Hierarchical structure.
• The topmost node, which does not have any parent in the tree is called the root of the tree. Each node will contain some data, it can be of any type and may contain a link or reference to some other node which is called its children.
  
• Children of the same parent are called siblings.
• Any node with no children is known as a leaf.
• The links in a tree are not bi-directional. We can go in only one direction.
  
• If we can go from a node to another node in a linked list, then the other node ( top node ) is known as the ancestor of the other node, and the other node is known as the descendant of the top node.
• The tree can be called a recursive data structure. We can define a tree recursively as a structure consisting of a distinguished node called root and some subtrees and arranged so that the root will consist of the link to the root of all the subtrees.
• In a Tree with N nodes, there will be N-1 edges or links ( the connection between a node to node ). One incoming edge for each node except for the root node.
• The depth of a node in a tree can be defined as the length of the path from the root to that node or the Number of edges in the path from the root to that node. The depth of the root node is zero.
  
• The height of a node in a tree can de be defined as the longest path from the node to a leaf. The height of the leaf node is zero. The height of an empty tree is -1.
  
• The height of a tree is defined as the height of the root node.

Binary Tree:

• A Binary Tree is a tree in which each node can have at most two children.
• A node in a binary tree can be defined as: 
• struct Node 
• {
• int data;
• Node* left;
• Node* right;
• };
• Struct or Proper Binary Tree is a tree in which each node can have either 2 or 0 children.
• Complete Binary Tree is a binary tree in which all levels except level possibly the last are completely filled and all nodes are as left as possible. 
• The maximum number of nodes at a level i = 2^i.
•  A perfect Binary Tree is a binary tree in which all levels are completely filled.
• Maximum number of nodes in a perfect tree with height h  = 2^0 + 2^1 + ..... + 2^h  = (2^h+1)-1 = 2^(number of levels) - 1
  
• The cost of operations in a binary tree depends on the height of the tree.
• The minimum height possible with n nodes is log base 2 (n) [ Time complexity will be O(log base 2 (n)) and maximum height possible is n-1 [ Time complexity will be O(n) ].
  
• A balanced Binary Tree is a binary tree in which the difference between the height of the left and right subtree for every node is one not more than k (mostly 1).
• We can implement a binary tree using a) dynamically created nodes. b) arrays.
• If a binary tree is implemented using arrays then the left child index = 2i+1 and the right child index will be 2i+2 for a node at index i.
  
• Applications:

1. Storing Naturally Hierarchical data. Example: File system
2. Organizing data for quick search, insertion, deletion
3. Trie (Dictionary)
4. Network Routing Algorithm

 

Binary Search Tree:

• A binary Search Tree is a Binary Tree in which for each node, the value of all the nodes in the left subtree is lesser or equal and the value of all the nodes in the right subtree is greater.
  
•  We can perform a Binary Search in a sorted array in O(log n) time. 
• Process of Binary Search:

1. First, we sort the array,  and then we will define the search space by start and end. 
2. Now, we compare the number to be searched with the mid element of the search space.
3. If the number we are comparing is less than the mid element, then we will search in the left half else we will search in the right half.
4. And then we will compare the number with the mid element the left half and the process continues until the number is found.
5. And for the n elements the search space will reduce in the order n, n/2, n/4, ...1
6. If the elements are stored in a binary search tree, then performing these operations will be easy.

 

Binary Search Tree Insertion In Iterative Method:

/* Insert Function in Iterative Method */
BSTNode* Insert(BSTNode* root, int data){
    BSTNode* newNode = GetNewNode(data);         // create a BSTNode with data field as data to be inserted
    if(root==NULL){                  // if the BST is empty
        root = newNode;             // we will insert the newNode at the root
        return root;
    }
    
    BSTNode* temp= root;           
    BSTNode* leafN = NULL;
    while(temp!=NULL){             /* Traversal overall the BSTree to find the leaf Node, which will be the parent of newNode*/
        leafN = temp;              /* leafN stores the address of the leafNode */
        if(data<=root->data){      /* if data is lessthan the root node data value */
            temp = temp->left;  /* the traversal will go in the left direction */
        }
        else {                   /* if data is greaterthan the root node data value */
            temp = temp->right;  /* the traversal will go in the right direction and finally we will reach the leaf Node */
        }
    }
    if(leafN==NULL){             // if leafNode = NULL
        leafN = newNode;        // we will insert newNode at leafNode
    }
    else if(data<=leafN->data){  // if inserting data is lessthan leaf Node data value
        leafN->left = newNode;   // we will insert the newNode at left pointer of Leaf Node
    }
    else {
        leafN->right = newNode; // else we will insert the newNode at right pointer of Leaf Node
    }
    return root;
}

 

Binary Search Tree Implementation In C++:

 

#include<iostream>
using namespace std;

struct BSTNode {
    int data;
    BSTNode* left;
    BSTNode* right;
};


BSTNode* GetNewNode(int data){              
    BSTNode* newNode = new BSTNode();
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

BSTNode* Insert(BSTNode* root, int data){         //Function TO Insert elements in the binary tree
    if(root==NULL){
        root = GetNewNode(data);
        return root;
    }
    else if(data<= root->data){
        root->left = Insert(root->left, data);
    }
    else {
        root->right = Insert(root->right, data);
    }
    return root;
}

bool Search(BSTNode* root, int data){         // Function to search an elemenet in the binary tree
    if(root == NULL) return false;
    else if(data== root->data) return true;
    else if(data<=root->data) return Search(root->left, data);
    else return Search(root->right, data);
}



/* Finding Minimum and Maximum Element in a tree using recursion method */

int FMin(BSTNode* root){   // Iterative method to find the minimum element in a tree
    if(root==NULL){
        cout<<"Error: Tree is Empty\n";
        return -1;
    }
    BSTNode* temp = root;
    while(temp->left!=NULL){
        temp=temp->left;
    }
    return temp->data;
}

int FMax(BSTNode* root){    // Iterative method to find the maximum element in a tree
    if(root==NULL){
        cout<<"Error: Tree is Empty\n";
        return -1;
    }
    BSTNode* temp = root;
    while(temp->right!=NULL){
        temp=temp->right;
    }
    return temp->data;
}



/* Finding Minimum and Maximum Element using recursion */

// int Fminr(BSTNode* root){      // recursion method to find minimum Element
//     BSTNode* temp = root;
//     if(root==NULL){
//         cout<<"Error: Tree Is Empty";
//         return -1;
//     }
//     else if(temp->left==NULL){
//         return temp->data;
//     }
//     else if(temp->left!=NULL){
//         Fminr(temp->left);
//     }
// }

// int Fmaxr(BSTNode* root){       // recursion method to find Maxiumum Element
//     BSTNode* temp = root;
//     if(root==NULL){
//         cout<<"Error: Tree Is Empty";
//         return -1;
//     }
//     else if(temp->right==NULL){
//         return temp->data;
//     }
//     else if(temp->right!=NULL){
//         Fminr(temp->right);
//     }
// }


int FindHeight(BSTNode* root){             // Function to find the height of the binary search Tree
    if(root==NULL){                       
        return 0;
    }
    else {
        int lHeight = FindHeight(root->left);
        int rHeight = FindHeight(root->right);
        if(lHeight>rHeight) return lHeight+1;
        else return rHeight+1;
    }
}



int main(){
    BSTNode* root = NULL;
    root = Insert(root,15);
    root = Insert(root,13);
    root = Insert(root,19);
    root = Insert(root,7);
    root = Insert(root,14);
    root = Insert(root,16);
    root = Insert(root,20);
    root = Insert(root,4);
    root = Insert(root,8);
    int number;
    
    // cout<<"Enter a number to search: \n";
    // cin>>number;
    // if(Search(root,number) == true) cout<<number<<" is Found \n";
    // else cout<<number<<" is not found\n";
    cout<<FMin(root)<<endl;
    cout<<FindHeight(root);
    
}