Binary Search Tree
A binary tree with an ordering invariant that makes search, insert, and delete O(log n).
- 1 Lesson
Dry-run engine
BST Insert
The ordering invariant lets every comparison throw away an entire subtree.
- Input · Insert key
- key = 7
- Output · Result
- Press play to run it
How it works
At each node compare key with the node's value: smaller goes left, larger goes right. The first null child you reach is where the new node is linked in.
heap_nodes[7] · ordered
- key7
- curr8 @0x5a10
- Compare7 < 8 → left
- Depth0
Every node holds a value plus two child addresses. Start at the root, 8 (0x5a10). 7 < 8, so go left — the subtree {10, 14} can't hold 7 and is never read.
1 / 4
Course Contents
Related courses
- ArraysContiguous, indexable memory — the foundation almost every other data structure builds on.12 lessons · 16 problems
- StringsCharacter arrays with their own set of classic patterns — two pointers, sliding window, and more.19 lessons · 19 problems
- Linked ListNodes linked one direction by pointers instead of contiguous memory.4 lessons · 12 problems