Videos / DSA

Episode 16 of 22 · DSA, end to end

Binary trees and binary search trees: recursion with a shape

Chapters

1. A bracket inside a bracket0:00
2. The struct is the definition0:17
3. Root, leaf, edge, subtree0:33
4. Depth down, height up0:49
5. Full, complete, perfect1:05
6. Balanced means short1:24
7. One visit, three places1:42
8. Preorder, the parent first1:59
9. Inorder, the node in the middle2:14
10. Postorder, children first2:30
11. Level order wants a queue2:48
12. One row at a time, and its cost3:04
13. A signpost at every fork3:23
14. The check almost everyone writes3:40
15. Carry a range downward3:56
16. Search is the walk4:15
17. Insert arrives as a leaf4:30
18. Delete has three cases4:46
19. Every cost is the height5:04
20. The list wearing pointers5:19
21. Twenty versus a million5:36
22. Sorted input is the normal case5:54
23. One rotation6:12
24. A rule for when to rotate6:30
25. Ask both, then decide6:49
26. Fill in the combine step7:07
27. Context down, answers up7:24
28. Diameter7:43
29. Lowest common ancestor8:01
30. Path sums go down8:19
31. Flatten it onto one line8:37
32. One walk is not enough8:53
33. Two walks, split and recurse9:10
34. The pair that does not work9:28
35. Write the gaps down9:46
36. A search tree needs less than that10:04
37. The whole thing10:22

Binary trees and binary search trees: recursion with a shape. Look at a tournament bracket. The final sits at the top, and underneath it are two smaller brackets that look exactly like the whole thing. That is the entire definition of a binar

Mark as watchedSaved in this browser only.