Binary trees, BSTs, and tree traversals. Foundation for many interview problems.
Time
BST Search/Insert/Delete: O(log n) avg, O(n) worst
Space
O(n)
Problems
5 must-do
| # | Problem | Difficulty | Asked At |
|---|---|---|---|
| 1 | Maximum Depth of Binary Tree | Easy | Google Amazon Meta |
| 2 | Validate Binary Search Tree | Medium | Microsoft Amazon Google |
| 3 | Binary Tree Level Order Traversal | Medium | Amazon Meta Microsoft |
| 4 | Lowest Common Ancestor | Medium | Google Meta Amazon |
| 5 | Serialize and Deserialize Binary Tree | Hard | Google Amazon Microsoft |
Most tree problems can be solved recursively
Inorder traversal of BST gives sorted order
Height of balanced tree = O(log n), skewed tree = O(n)
BFS uses queue; DFS uses stack/recursion
