🌳🔍
Binary Search Tree: every left child is smaller, every right child is larger. This one rule makes searching as fast as flipping to the middle of an ordered list — O(log n) time!
Mode:
Speed:
Nodes: 0
Height: 0
Min: —
Max: —
🌱
Tree is empty
Insert a value to start!
In-order:
Insert
Quick presets:
Search
Delete
Traversals
🌳
Ready
Insert a value or click a preset to begin.
🔑 BST Property
All left descendants
<
Node
<
All right descendants
This property makes search, insert, and delete all O(log n) in a balanced tree.
🌳
Binary Search Tree (BST)
A self-organizing data structure that keeps everything sorted
🌳
A Binary Tree is a tree where each node has at most 2 children: a left child and a right child.
🔑
In a BST, every node's left subtree contains only values smaller than it, and its right subtree contains only values larger than it.
📏
This ordering rule makes it possible to search in O(log n) — like binary search, but on a tree!
⚠️
A BST can become skewed (like a linked list) if you insert values in sorted order. Then search is O(n) worst case. Self-balancing trees (AVL, Red-Black) fix this.
➕
Insert: Compare with root → go left if smaller, right if larger → repeat until you find an empty spot. Place the new node there.
🔍
Search: Same comparison path as insert. If you reach a null, the value doesn't exist.
🗑️
Delete (3 cases):
① Leaf node → simply remove
② One child → replace node with its child
③ Two children → replace with in-order successor (smallest in right subtree)
① Leaf node → simply remove
② One child → replace node with its child
③ Two children → replace with in-order successor (smallest in right subtree)
⬅➡
In-order (L→Root→R): Visits nodes in sorted ascending order. Used to get a sorted list from a BST.
⬆
Pre-order (Root→L→R): Visits root first. Used to copy or serialize the tree.
⬇
Post-order (L→R→Root): Visits root last. Used to delete a tree or evaluate expression trees.
🔵
Level-order (BFS): Visits level by level using a queue. Gives breadth-first view of the tree.
📂
File systems use tree structures to organize folders — finding a file is essentially a tree search.
🗄️
Database indexes (B-trees, which are generalized BSTs) make SQL queries like WHERE id = 42 run in milliseconds on millions of rows.
🌐
Auto-complete and spell-checking use tries (prefix trees), a variant of binary trees.
🎮
Game AI uses game trees (binary or N-ary) and the Minimax algorithm to decide the best move.