Binary Search Tree (BST)

Definition

A Binary Search Tree (BST) is a binary tree in which every node follows the property:

left subtree < node < right subtree

This must be true recursively for all nodes.

Properties of BST

Node Structure in Java

class TreeNode {
    int val;
    TreeNode left, right;

    TreeNode(int val) {
        this.val = val;
    }
}

Core BST Operations (Java)

1. Insertion

public TreeNode insert(TreeNode root, int key) {
    if (root == null) return new TreeNode(key);
    if (key < root.val) root.left = insert(root.left, key);
    else if (key > root.val) root.right = insert(root.right, key);
    return root;
}

2. Search

public boolean search(TreeNode root, int key) {
    if (root == null) return false;
    if (key == root.val) return true;
    else if (key < root.val) return search(root.left, key);
    else return search(root.right, key);
}

3. Deletion

public TreeNode delete(TreeNode root, int key) {
    if (root == null) return null;

    if (key < root.val) root.left = delete(root.left, key);
    else if (key > root.val) root.right = delete(root.right, key);
    else {
        if (root.left == null) return root.right;
        if (root.right == null) return root.left;
        TreeNode minNode = getMin(root.right);
        root.val = minNode.val;
        root.right = delete(root.right, minNode.val);
    }
    return root;
}

private TreeNode getMin(TreeNode node) {
    while (node.left != null) node = node.left;
    return node;
}

Traversals (DFS)

Inorder (Left → Root → Right)

public void inorder(TreeNode root) {
    if (root != null) {
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }
}

Preorder and Postorder also follow standard recursion.

Time and Space Complexity

Worst-case occurs when the tree becomes skewed (like a linked list).

AVL Tree (Adelson-Velsky and Landis Tree)

Definition

AVL Tree is a self-balancing BST where for every node:

|height(left) - height(right)| <= 1

Properties of AVL Tree

Balance Factor

balanceFactor = height(left subtree) - height(right subtree)

Rotations (for balancing)

1. Right Rotation (LL Case)

private TreeNode rightRotate(TreeNode y) {
    TreeNode x = y.left;
    TreeNode T2 = x.right;

    x.right = y;
    y.left = T2;

    y.height = Math.max(height(y.left), height(y.right)) + 1;
    x.height = Math.max(height(x.left), height(x.right)) + 1;

    return x;
}

2. Left Rotation (RR Case)

private TreeNode leftRotate(TreeNode x) {
    TreeNode y = x.right;
    TreeNode T2 = y.left;

    y.left = x;
    x.right = T2;

    x.height = Math.max(height(x.left), height(x.right)) + 1;
    y.height = Math.max(height(y.left), height(y.right)) + 1;

    return y;
}

3. Left-Right Rotation (LR Case)

// Step 1: Left Rotate
root.left = leftRotate(root.left);
// Step 2: Right Rotate
return rightRotate(root);

4. Right-Left Rotation (RL Case)

// Step 1: Right Rotate
root.right = rightRotate(root.right);
// Step 2: Left Rotate
return leftRotate(root);

AVL Insertion (Java Full Logic)

class AVLNode {
    int val, height;
    AVLNode left, right;

    AVLNode(int val) {
        this.val = val;
        this.height = 1;
    }
}

class AVLTree {
    private int height(AVLNode node) {
        return node == null ? 0 : node.height;
    }

    private int getBalance(AVLNode node) {
        return node == null ? 0 : height(node.left) - height(node.right);
    }

    private AVLNode rightRotate(AVLNode y) {
        AVLNode x = y.left;
        AVLNode T2 = x.right;
        x.right = y;
        y.left = T2;
        y.height = Math.max(height(y.left), height(y.right)) + 1;
        x.height = Math.max(height(x.left), height(x.right)) + 1;
        return x;
    }

    private AVLNode leftRotate(AVLNode x) {
        AVLNode y = x.right;
        AVLNode T2 = y.left;
        y.left = x;
        x.right = T2;
        x.height = Math.max(height(x.left), height(x.right)) + 1;
        y.height = Math.max(height(y.left), height(y.right)) + 1;
        return y;
    }

    public AVLNode insert(AVLNode node, int key) {
        if (node == null) return new AVLNode(key);
        if (key < node.val) node.left = insert(node.left, key);
        else if (key > node.val) node.right = insert(node.right, key);
        else return node;

        node.height = 1 + Math.max(height(node.left), height(node.right));
        int balance = getBalance(node);

        // LL
        if (balance > 1 && key < node.left.val) return rightRotate(node);
        // RR
        if (balance < -1 && key > node.right.val) return leftRotate(node);
        // LR
        if (balance > 1 && key > node.left.val) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }
        // RL
        if (balance < -1 && key < node.right.val) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        return node;
    }
}

AVL Tree Time Complexity

Summary