Binary search trees explained from zero with one town where every road splits in two. 100,000 random house numbers: built in 0.14 seconds. The exact same numbers in sorted order: 211 seconds, 1,500 times slower. Same code, same numbers, different shape.
Episode 10 of Algorithms Unboxed, a free course from zero to mastery.
You’ll learn:
• What a tree is: root, children, parent, leaf, height, subtree
• The one rule of a binary search tree (the whole side, not just the child)
• Search, insert and delete step by step (the two-children case)
• In-order, pre-order, post-order and level-order traversals
• Why sorted input turns the tree into a linked list: O(n)
• Inside the computer: a node with a key and two addresses
• The interview question: Validate Binary Search Tree (LeetCode 98)
Every number is a real run on our server (Python 3.11):
• 100,000 random keys: built in 0.14 s, height 41, one search ~2 µs
• 100,000 sorted keys: height 100,000, one search 3.5 ms; the recursive walk crashed at 1,000 houses
• Sorted list + bisect: search 0.8 µs, but inserting the same keys took 0.66 s
• Range query (94 keys): dictionary 2.8 ms vs tree 27 µs, 100x faster
Have you ever had code that was fast on random data and crawled on sorted data? Tell us in the comments.
Chapters:
0:00 0.14 s vs 211 s: same numbers, different shape
0:28 What a tree is
1:16 The binary search tree rule
1:43 Search step by step
2:14 Insert
2:32 Delete (the tricky case)
2:55 Traversals: in, pre, post, level order
3:37 Sorted data: the tree becomes a road
4:12 Inside the computer
4:31 The code in Python
4:55 Real benchmark: tree vs bisect vs dict
5:40 Trees around you
6:19 When to use a BST (and when not)
6:40 Interview: Validate BST (LeetCode 98)
7:12 The answer + next episode
Next episode: balanced trees. AVL, red-black and the B-trees inside every database.
Subscribe for the whole course: https://www.youtube.com/@TechUnboxedLab?sub_confirmation=1
Photos:
orgchart: “Early NASA organizational chart” by chrisspurgeon (PDM 1.0) https://www.flickr.com/photos/41663378@N00/287136251
bracket: “Now, that is a bracket!” by frankieleon (BY 2.0) https://www.flickr.com/photos/23307937@N04/16671230120
questions: “Question Mark” by ryanmilani (BY 2.0) https://www.flickr.com/photos/51029297@N00/5275403364
html: “HTML Code” by Sebastian Fuss (BY-SA 2.0) https://www.flickr.com/photos/37868239@N02/5848333881
#datastructures #trees #algorithms
source
