📘 Binary Search Tree (BST)

A Binary Search Tree (BST) is a binary tree with the following properties:

1. Each node contains a key (value).

2. The left subtree of a node contains only nodes with keys less than the node’s key.

3. The right subtree of a node contains only nodes with keys greater than the node’s key.

4. Both left and right subtrees must also be binary search trees.

5. No duplicate keys are allowed (in standard BSTs).

👉 Because of these properties, searching, insertion, and deletion can be done efficiently, usually in O(log n) time for balanced trees.

Algorithm: Insert a Node in BST 

👉 At each step:

• Compare the new value with the current node.

• If smaller, go left.

• If greater, go right.

• If empty spot is found, insert the new node there.

Node* insert(Node* root, int key) {
    // If tree is empty, create new node
    if (root == NULL) {
        root = createNode(key);
        return root;
    }

    // If key is smaller, go to left subtree
    if (key < root->data)
        root->left = insert(root->left, key);

    // If key is greater, go to right subtree
    else if (key > root->data)
        root->right = insert(root->right, key);

    // If key is equal, duplicates not allowed
    return root;
}

📘 Example of Creating a BST
Suppose we want to insert the following sequence into an empty BST:
[50, 30, 70, 20, 40, 60, 80]
Step 1: Insert 50
Tree is empty, so 50 becomes root.
   50

Step 2: Insert 30
30 < 50 → insert into left subtree of 50.
    50
   /
 30

Step 3: Insert 70
70 > 50 → insert into right subtree of 50.
    50
   /  \
 30    70

Step 4: Insert 20
20 < 50 → go left

20 < 30 → insert left of 30.
      50
     /  \
   30    70
  /
20

Step 5: Insert 40
40 < 50 → go left

40 > 30 → insert right of 30.
      50
     /  \
   30    70
  /  \
20    40

Step 6: Insert 60
60 < 70 → insert left of 70.
      50
     /  \
   30    70
  /  \   /
20    40 60

Step 7: Insert 80
80 > 70 → insert right of 70.
      50
     /  \
   30    70
  /  \   / \
20    40 60 80

✅ Final BST (after inserting [50, 30, 70, 20, 40, 60, 80]):
         50
       /    \
     30      70
    /  \    /  \
  20   40  60   80