Binary Search Tree (BST) Visualization & Animation

Ordered binary tree where left < node < right; O(log n) average search, insert, and delete.

## What is it? A Binary Search Tree (BST) is a binary tree where every node satisfies the BST property: all values in the left subtree < node value < all values in the right subtree. This property enables efficient search, insertion, and deletion. ## How it works **Search:** - Compare target with current node; go left if smaller, right if larger; return node if equal **Insert:** - Search for the position where the new node would be, insert there as a leaf **Delete:** - Leaf → remove directly - One child → replace node with its child - Two children → replace with in-order successor (smallest in right subtree), delete that successor **In-order traversal** produces elements in sorted order. ## When to use - Dynamic sorted sets (frequent insert/delete + search) - Range queries (all elements between A and B) - Predecessor/successor queries ## Key Points - Average case: O(log n) for all operations - Worst case: O(n) when tree becomes a chain (degenerate BST from sorted input) - Balanced BSTs (AVL, Red-Black) guarantee O(log n) worst case - In-order traversal → sorted sequence

Category: data-structure

Difficulty: intermediate

Time Complexity: O(log n) avg, O(n) worst

Space Complexity: O(n)

Binary Search Tree (BST)

intermediate

Ordered binary tree where left < node < right; O(log n) average search, insert, and delete.

GFG
Enter node values and press Play to build the tree
Tree is empty. Press Play to build, or use the Search / Delete buttons.