ALGOSECHEL :: Binary Search Tree

PRESETS:

[ READY ] Enter a key and use the controls above. Try the preset datasets to get started.

Default Search path Current Found / Inserted Range match Deleted

:: Tree Stats

Nodes

Height

—

Min

—

Max

:: In-Order Traversal

—

In-order traversal of BST always yields keys in sorted ascending order — the foundation of database range queries.

:: BST Property

For every node N:
All keys in left subtree < N.key
All keys in right subtree > N.key

This ordering guarantees O(log n) search by halving the search space at each comparison.

:: Time & Space Complexity

Operation	Best	Average	Worst (unbalanced)	Space
Search	O(log n)	O(log n)	O(n)	O(1)
Insert	O(log n)	O(log n)	O(n)	O(1)
Delete	O(log n)	O(log n)	O(n)	O(1)
Range Query	O(log n + k)	O(log n + k)	O(n)	O(k)
In-Order Traversal	O(n)	O(n)	O(n)	O(n)
Min / Max	O(log n)	O(log n)	O(n)	O(1)
Build from n keys	O(n log n)	O(n log n)	O(n²)	O(n)

k = number of keys returned in range query. Worst case occurs on sorted input (degenerates to linked list). AVL/Red-Black trees guarantee O(log n) by self-balancing.

:: BST vs Database Index Structures

Structure	Search	Range Query	Disk Friendly	Used In
BST	O(log n)	O(log n + k)	Poor	In-memory indexes
AVL Tree	O(log n)	O(log n + k)	Poor	In-memory, strict balance
Red-Black Tree	O(log n)	O(log n + k)	Poor	Linux kernel, Java TreeMap
B-Tree	O(log n)	O(log n + k)	Excellent	Filesystems, DB primary keys
B+Tree	O(log n)	O(log n + k)	Excellent	MySQL InnoDB, PostgreSQL
Hash Index	O(1)	N/A	Varies	Equality-only lookups

:: Why Databases use B+Tree over plain BST

Disk I/OB+Trees have high branching factors (100–1000 children/node), meaning fewer disk reads per lookup. A BST node holds one key; a B+Tree page holds hundreds.

Range ScansB+Trees store all data in leaf nodes linked as a doubly-linked list — range queries simply scan leaves sequentially. BST range queries require recursive traversal.

Cache EfficiencyB+Tree pages align with OS page cache (4KB–16KB). BST nodes are heap-allocated and pointer-chased, causing cache misses on every level.

Guaranteed BalanceB-Trees self-balance on every insert/delete via splits and merges. BST can degenerate to O(n) without explicit rebalancing logic.