Fundamentals of Binary Search Tree (C++)

Binary Search Trees (BSTs) are one of the fundamental data structures in computer science. They store data hierarchically, allowing efficient operations like insertion, deletion, and search.

This blog will walk you through implementing a simple Binary Search Tree (BST) in C++.

Code Walkthrough

1. Include Necessary Libraries:

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

   • The #include <bits/stdc++.h> is a comprehensive header file that includes most C++ standard libraries.

   • The using namespace std; statement allows direct use of standard library components like cout.

2. Define the Node Structure:

    typedef struct Node Node;
   
    struct Node{ 
        int data; 
        Node *left, *right; 
    };
   

   • Node Structure: Each node of the BST contains:

     • data: The value stored in the node.

     • left: A pointer to the left child node.

     • right: A pointer to the right child node.

3. Insertion in the BST:

    Node* insert(Node* root, int data){
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = data;
        newNode->left = newNode->right = NULL;
        if (!root) return newNode;
        if (data < root->data) 
            root->left  = insert(root->left, data); 
        else if (data > root->data) 
            root->right = insert(root->right, data);
        return root; 
    }
   

   Key Steps:

   1. Memory Allocation:

      • A new node is dynamically allocated using malloc.

      • The node's data is set, and its left and right pointers are initialized to NULL.

   2. Base Case:

      • If root is NULL, the new node becomes the root of the tree.

   3. Recursive Insertion:

      • If data is less than root->data, it is inserted into the left subtree.

      • If data is greater than root->data, it is inserted into the right subtree.

   4. Return the Root Node:

      • After insertion, the updated tree is returned.

4. In-Order Traversal:

    void inOrder(Node* root){
        if(root){
            inOrder(root->left);
            cout<<root->data<<" ";
            inOrder(root->right);
        }
    }
   

   Key Steps:

   1. Left-Root-Right Traversal:

   2. • Recursively traverse the left subtree.

        • Print the value at the current node.

        • Recursively traverse the right subtree.

   3. Result:

      • In-order traversal produces a sorted sequence of the BST elements.

5. Main Function:

    int main(){
        Node *root = NULL; 
        root = insert(root, 50); 
        insert(root, 30); 
        insert(root, 20); 
        insert(root, 40); 
        insert(root, 70); 
        insert(root, 60); 
        insert(root, 80);
        inOrder(root);
        return 0;
    }
   

   Key Steps:

   1. Initialize the Tree:

      • The root of the tree is initialized to NULL.

   2. Insert Elements:

      • Elements (50, 30, 20, 40, 70, 60, 80) are inserted into the BST.

   3. Perform In-Order Traversal:

      • The inOrder function is called to print the elements in sorted order.

   4. Output:

      • The output of the in-order traversal is:
        20 30 40 50 60 70 80

Visualization

Tree Structure:

After inserting the elements, the BST structure looks like this:

         50
       /    \
     30      70
    /  \    /  \
  20   40  60   80

Traversal Steps:

• Start with the leftmost node (20).

• Print the nodes in ascending order as you traverse back up.

Advantages of Binary Search Tree

1. Efficient Searching:The averagee time complexity for search operations is O(log⁡ n).

2. Dynamic Size: Nodes can be inserted or deleted dynamically without resizing.

3. Sorted Data Representation: In-order traversal provides a sorted sequence of elements.

Challenges

1. Unbalanced Tree: If the input data is sorted, the tree becomes skewed, degrading performance to O(n).

2. Memory Management: Using malloc requires careful memory management.

Conclusion

This implementation demonstrates the basics of a Binary Search Tree in C++. By understanding its structure, insertion logic, and traversal, you can extend the BST to include advanced operations like deletion, balancing, or range queries.

Feel free to experiment with this code and enhance it for your specific use case!

References

1. Find the code for the above explanation here.