1. What is a Binary Search Tree (BST)?

A Binary Search Tree (BST) is a special kind of binary tree that maintains a specific order among its elements (nodes), which makes it efficient for operations like search, insert, and delete.

2. Definition:

A Binary Search Tree is a binary tree in which:

• Every node has at most two children: left and right.
• For any given node with value X:
  • All nodes in the left subtree of X have values less than X.
  • All nodes in the right subtree of X have values greater than X.

This property is recursively true for all nodes in the tree.

3. Properties of BST

Property	Description
Binary Tree	Every node has 0, 1, or 2 children.
Ordering Property	Left < Root < Right
No Duplicate Nodes	Typically, duplicates are not allowed in classic BSTs.
Search Time	Best case: O(log n); Worst case: O(n) (if skewed)
Balanced BST	Keeps height ≈ log(n); ensures faster operations

4. Visual Representation

Let’s take an example of values:

50, 30, 70, 20, 40, 60, 80

Here’s how they would be structured in a BST:

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

Each node follows the BST rule:

• 30 < 50, 70 > 50
• 20 < 30 < 40
• 60 < 70 < 80

5. Java Representation of a Binary Search Tree

Step 1: Define the Node Class

Each node contains:

• An integer data
• A left child
• A right child

public class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;

    public TreeNode(int value) {
        this.data = value;
        this.left = null;
        this.right = null;
    }
}

Step 2: Define the BinarySearchTree Class

This class contains:

• A root node
• Methods to insert, search, and traverse

public class BinarySearchTree {
    TreeNode root;

    public BinarySearchTree() {
        root = null;
    }

    // Insert a node into the BST
    public void insert(int value) {
        root = insertRecursive(root, value);
    }

    private TreeNode insertRecursive(TreeNode node, int value) {
        if (node == null) {
            return new TreeNode(value);
        }

        if (value < node.data) {
            node.left = insertRecursive(node.left, value);
        } else if (value > node.data) {
            node.right = insertRecursive(node.right, value);
        }

        return node;
    }

    // Search for a value
    public boolean search(int value) {
        return searchRecursive(root, value);
    }

    private boolean searchRecursive(TreeNode node, int value) {
        if (node == null) {
            return false;
        }

        if (value == node.data) {
            return true;
        }

        return value < node.data
            ? searchRecursive(node.left, value)
            : searchRecursive(node.right, value);
    }

    // Inorder Traversal (Left -> Root -> Right)
    public void inorderTraversal() {
        inorderRecursive(root);
    }

    private void inorderRecursive(TreeNode node) {
        if (node != null) {
            inorderRecursive(node.left);
            System.out.print(node.data + " ");
            inorderRecursive(node.right);
        }
    }
}

Step 3: Main Method to Test the BST

public class BSTDemo {
    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();

        int[] values = {50, 30, 70, 20, 40, 60, 80};

        for (int value : values) {
            bst.insert(value);
        }

        System.out.print("Inorder Traversal: ");
        bst.inorderTraversal();  // Output should be sorted

        System.out.println("\nSearch 40: " + bst.search(40)); // true
        System.out.println("Search 90: " + bst.search(90));   // false
    }
}

6. Advantages of BST

• Easy to implement and understand
• Efficient O(log n) time for insert/search/delete (if balanced)
• Supports in-order traversal to get sorted order

7. Disadvantages of BST

• Can become skewed (like a linked list) in worst-case, making operations O(n)
• Not self-balancing — requires external logic or different tree (like AVL/Red-Black)

---

8. When to Use a BST

Use a BST when:

• You need fast insertion, deletion, and lookup.
• You want to maintain elements in sorted order.
• You do not expect the input data to be sorted (which would make it skewed).