DSA sheet · Trees · Binary Search Tree pattern
BST DSA Notebook
My study notes on Binary Search Trees from the pattern-wise DSA playlist. Each page is written so that a beginner (or me, after forgetting everything) can read it once and understand the intuition, how every condition is derived, the Python code line by line, and a full dry run.
The one rule behind every page
In a BST, for every node: all values in its left subtree are smaller and all values in its right subtree are bigger. That holds for the whole subtree, not just the direct children.
Two results we keep using: ① at each node you can throw away one half, like binary search; ② an inorder walk (left → node → right) visits the values in sorted order.
Two results we keep using: ① at each node you can throw away one half, like binary search; ② an inorder walk (left → node → right) visits the values in sorted order.
Every page follows the same order:
① question in simple words → ② constraints → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ line by line → ⑧ dry run → ⑨ complexity & remember
Basics: walk down one path
- 2Search in a BSTrecursion · loop
- 3Insert into a BSTrecursion · loop
- 4LCA of a BSTrecursion · loop
- 8Closest Node in a BSTinorder → walk down
- 14Predecessor & Successor in BSTbrute → walk down
Building & changing a BST
Inorder = sorted
- 5Validate BSTbrute → range
- 6BST Iteratorbrute → stack
- 7Two Sum IV (BST)4 approaches
- 11Kth Smallest in a BSTsort → stack
- 12Recover BST3 approaches
- 13BST to Greater Treebrute → reverse inorder
Bottom-up (postorder)
Numbers are the order in the playlist. "Next →" at the top of each page follows that order. The general binary tree problems are in the separate Binary Tree DSA Notebook.