Binary Search Tree (BST) Visualization

What is a Binary Search Tree?

A Binary Search Tree (BST) is a specialized binary tree where nodes are organized according to a specific ordering property: for each node, all values in the left subtree are less than the node's value, and all values in the right subtree are greater. This property enables efficient searching, insertion, and deletion operations.

BSTs provide O(log n) average time complexity for search, insert, and delete operations when balanced. However, in the worst case (skewed tree), these operations can degrade to O(n). Self-balancing variants like AVL and Red-Black trees maintain balance to ensure optimal performance.

Key Characteristics

Ordered Structure: Left child < Parent < Right child
Efficient Search: Binary search algorithm applied to tree structure
No Duplicates: Typically doesn't allow duplicate values
In-Order Traversal: Visits nodes in sorted ascending order
Dynamic Operations: Supports insertion and deletion while maintaining order

Interactive BST simulation. Insert numeric values and watch them automatically position according to BST rules.

Insert Value:

Search Value:

Actions:

Insert a value to create the root node and start building your BST

How to Use

Step 1: Enter a number and click "Insert Node" to add it to the tree.

Step 2: The node will automatically be placed in the correct position based on BST rules.

Step 3: Continue inserting values to build your tree structure.

Step 4: Use "Search" to find a value - found nodes will highlight in green for 2 seconds.

Note: Smaller values go left, larger values go right. Duplicates are not allowed.

BST Properties

Left Subtree: All nodes with values less than the parent.

Right Subtree: All nodes with values greater than the parent.

Unique Values: Each value appears at most once in the tree.

Recursive Property: Every subtree is also a valid BST.

In-Order Gives Sorted: In-order traversal produces values in ascending order.

Time Complexity

Search (Average): O(log n) - eliminates half of remaining nodes at each step.

Search (Worst): O(n) - when tree becomes skewed (like a linked list).

Insert (Average): O(log n) - finds correct position using binary search.

Delete (Average): O(log n) - finds node and restructures tree.

Space Complexity: O(n) - stores n nodes in the tree.

BST Operations

Insert: Compare with current node, go left if smaller, right if larger, until finding empty spot.

Search: Binary search from root; go left for smaller values, right for larger.

Delete: Find node, then handle three cases: leaf, one child, or two children (use inorder successor).

Min/Max: Follow leftmost path for minimum, rightmost path for maximum.

Inorder Successor: Smallest node in right subtree, or first right ancestor.

Validate BST: Check if tree satisfies BST property using range constraints.

Common BST Patterns

Validate BST: Track min/max bounds during recursion; each node must be within valid range.

Kth Smallest/Largest: Inorder traversal with counter, or augment nodes with subtree size.

LCA in BST: Use BST property; if both values less than root go left, both greater go right, else current is LCA.

Convert Sorted Array to BST: Pick middle element as root, recursively build left and right subtrees.

BST Iterator: Use stack to simulate inorder traversal; push all left children first.

Recover BST: Find two swapped nodes using inorder traversal, then swap their values.

Range Sum/Count: Use BST property to prune branches outside the target range.

C++

Java

Python

/* Binary Search Tree implementation in C */
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int value;
    struct Node* left;
    struct Node* right;
} Node;

Node* createNode(int value) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->value = value;
    node->left = node->right = NULL;
    return node;
}

Node* insert(Node* root, int value) {
    if (root == NULL) return createNode(value);
    if (value < root->value)
        root->left = insert(root->left, value);
    else if (value > root->value)
        root->right = insert(root->right, value);
    return root;
}

Node* search(Node* root, int value) {
    if (root == NULL || root->value == value)
        return root;
    if (value < root->value)
        return search(root->left, value);
    return search(root->right, value);
}

Node* minValueNode(Node* node) {
    Node* current = node;
    while (current && current->left != NULL)
        current = current->left;
    return current;
}

Node* deleteNode(Node* root, int value) {
    if (root == NULL) return root;
    if (value < root->value)
        root->left = deleteNode(root->left, value);
    else if (value > root->value)
        root->right = deleteNode(root->right, value);
    else {
        if (root->left == NULL) {
            Node* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            Node* temp = root->left;
            free(root);
            return temp;
        }
        Node* temp = minValueNode(root->right);
        root->value = temp->value;
        root->right = deleteNode(root->right, temp->value);
    }
    return root;
}

void inOrder(Node* root) {
    if (root) {
        inOrder(root->left);
        printf("%d ", root->value);
        inOrder(root->right);
    }
}

int main() {
    Node* root = NULL;
    root = insert(root, 50);
    insert(root, 30); insert(root, 70);
    insert(root, 20); insert(root, 40);
    printf("In-order: "); inOrder(root); // 20 30 40 50 70
    return 0;
}