Binary Tree and BST Cheat Sheet: Everything You Need Before Your Interview
- Inorder traversal of a BST always produces sorted output, which directly solves kth smallest, BST validation by traversal, and most range queries
- The classic BST validation bug checks only the parent node; the fix is passing min and max bounds down the recursion so every ancestor's constraint propagates
- Two DFS shapes cover most tree problems: return a subtree answer upward, or compute both children locally and return only one arm upward
- BST operations are O(log n) average but degrade to O(n) on a skewed tree; always state the worst case when discussing complexity in an interview
- BST delete has three cases: leaf node, one child, and two children — the two-child case overwrites with the inorder successor then deletes the successor
- Height vs depth: height is the longest downward path from a node; depth is the distance upward to the root — confusing them is a common four-bug interview killer
Twenty minutes before your interview starts, you're not going to spin up a LeetCode problem. You're going to open this page, read it once, and walk in like you've known this stuff forever.
Every fact here is something you already know. It's just not front-of-mind right now. The traversal that produces sorted output. The BST validation bug that trips senior engineers. The two DFS shapes that cover 80% of tree problems. Read it once. Close the tab. Go.
Tree Properties You Should Have Memorized
A tree with N nodes has exactly N-1 edges. Always. No exceptions. This comes up on problems where you need to count edges, and it's a nice grounding fact when everything else has gone blank.
Height = longest path from root to any leaf. A single node has height 0. A null pointer has height -1, which matters when you're recursing and want to avoid off-by-one errors in height calculations.
Depth of a node = its distance from the root. Root is depth 0.
For a perfect binary tree at height h:
| Metric | Formula |
|---|---|
| Total nodes | 2^(h+1) - 1 |
| Leaf nodes | 2^h |
| Height given n nodes | floor(log₂ n) |
For a complete binary tree: all levels full except possibly the last, which fills left to right. This is what heaps use. It lets you store the whole tree in a flat array: parent at index i, children at 2i+1 and 2i+2. Heaps feel like magic once this clicks.
For a skewed tree: height equals n-1. Every BST operation that's O(log n) on average degrades to O(n). Always mention this when you state BST complexity in an interview. Interviewers perk up when you say "assuming the tree is balanced" because most candidates don't.
The Four Traversals: Know What Each One Is For
| Traversal | Order | When to reach for it |
|---|---|---|
| Inorder | Left, Root, Right | BST problems needing sorted output; kth smallest; validation by sorted check |
| Preorder | Root, Left, Right | Serialize a tree; copy a tree; process parent before children |
| Postorder | Left, Right, Root | Compute height or diameter; problems needing children's answers first |
| Level order | BFS with queue | Row-by-row problems; right-side view; shortest path in unweighted tree |
All four run in O(n) time. Recursive DFS uses O(h) stack space. Level order uses O(w) space where w is the max width. In a perfect binary tree the last level alone holds n/2 nodes, so level order can hit O(n) in the worst case.
For iterative implementations (when the recursion depth is scary), see Binary Tree Traversal.
The BST Invariant and Why Inorder Works
For every node in a valid BST, all values in its left subtree are strictly less than the node, and all values in its right subtree are strictly greater. The entire subtree, not just the direct children.
That second sentence is doing a lot of work. Most interview bugs live exactly there.
As a direct consequence: an inorder traversal of a valid BST visits nodes in strictly ascending order. This one fact solves kth smallest, BST validation, and most range query problems. Tattoo it somewhere prominent.
The BST Validation Bug Everyone Writes First
def is_valid_bst(node): if not node: return True if node.left and node.left.val >= node.val: return False if node.right and node.right.val <= node.val: return False return is_valid_bst(node.left) and is_valid_bst(node.right)
This code looks completely reasonable. You checked the left child. You checked the right child. You recursed. Seems fine. Ship it.
It fails on this tree:
5
/ \
1 4
/ \
3 6
Node 3 is in the right subtree of 5, so it must be greater than 5. But 3 is not greater than 5. The code checks 3 against its parent (4), sees 3 < 4, decides everything is fine, and returns True. The tree is not valid. Your solution is confidently, silently wrong.
The fix: carry min and max bounds down through the recursion.
def is_valid_bst(node, min_val=float('-inf'), max_val=float('inf')): if not node: return True if not (min_val < node.val < max_val): return False return (is_valid_bst(node.left, min_val, node.val) and is_valid_bst(node.right, node.val, max_val))
Going left tightens the upper bound to the current node. Going right tightens the lower bound. Every ancestor's constraint propagates all the way down. You can't sneak a 3 past a 5 anymore.
O(log n) Average, O(n) Worst: Know the Difference
| Operation | BST average | BST worst (skewed) | Balanced BST |
|---|---|---|---|
| Search | O(log n) | O(n) | O(log n) |
| Insert | O(log n) | O(n) | O(log n) |
| Delete | O(log n) | O(n) | O(log n) |
| Min / Max | O(h) | O(n) | O(log n) |
| Inorder traversal | O(n) | O(n) | O(n) |
h = height. In a balanced tree, h = O(log n). In a skewed tree, h = O(n).
BST Delete Has Three Cases
- Leaf node: remove it directly.
- One child: replace the node with its single child.
- Two children: find the inorder successor (the smallest node in the right subtree). Copy its value into the current node. Delete the inorder successor from the right subtree. Because the inorder successor has no left child by definition, this deletion is always case 1 or case 2.
Case 3 is where candidates stumble. You're not removing the node in place. You're overwriting its value and deleting the successor downstream. The node stays where it is in the tree; only its value changes.
The Two DFS Shapes That Cover Most Tree Problems
Shape 1: Return the answer for each subtree to the parent.
def height(node): if not node: return -1 return 1 + max(height(node.left), height(node.right))
The function returns exactly what the parent needs. Use this when the answer at a node depends only on its children.
Shape 2: Use both children's values locally, return only one thing upward.
def diameter_of_binary_tree(root): max_diameter = [0] def depth(node): if not node: return 0 left = depth(node.left) right = depth(node.right) max_diameter[0] = max(max_diameter[0], left + right) return 1 + max(left, right) depth(root) return max_diameter[0]
The function uses left + right to update the global answer (a path that spans both children through this node), but returns only 1 + max(left, right) to the parent. A path going upward can only go in one direction. If you try to take both arms with you, you've got a Y shape, which is not a path.
Shape 2 appears in: diameter, binary tree maximum path sum, longest ZigZag path, any problem where the answer can cross the current node in both directions but cannot extend upward from both sides simultaneously.
Recursive DFS uses O(h) call stack space. No malloc. No new. Just you, the OS, and the hope that your tree is balanced.
recursive DFS: vibing on the call stack, enjoying O(h) space... on a perfectly balanced tree
Five Problems You Must Know Cold
Validate BST (LC 98). Pass min/max bounds through recursion. See above.
Kth Smallest in BST (LC 230). Inorder traversal visits nodes in sorted order. Count as you go. Return when count hits k. O(h + k) time, O(h) space.
Lowest Common Ancestor of a Binary Tree (LC 236). At each node, check whether targets appear in the left subtree, right subtree, or the current node itself. If targets are found on both sides (or one side plus the current node), the current node is the LCA. For a BST specifically: if both target values are less than root, recurse left; if both are greater, recurse right; otherwise root is the LCA.
See Lowest Common Ancestor of a Binary Tree for the full proof.
Convert Sorted Array to BST (LC 108). Always pick the middle index as root. Left half becomes the left subtree, right half becomes the right. This guarantees a height-balanced result and gives O(n) time.
Serialize and Deserialize Binary Tree (LC 297). Preorder traversal with explicit null markers works cleanly. On deserialization, consume tokens in the same preorder sequence: first token is root, then recursively build left and right subtrees from the remaining tokens. The null markers let you reconstruct the tree uniquely.
For more BST problems ranked by pattern, see Top 12 Binary Search Tree Interview Problems.
Which Language Brought a BST to the Party?
Java and C++ showed up with TreeMap. Python came with nothing and said "sortedcontainers is available if you allow external packages."
| Language | Built-in ordered structure |
|---|---|
| Java | TreeMap, TreeSet (Red-Black Tree, O(log n) per op) |
| C++ | std::map, std::set (Red-Black Tree, O(log n) per op) |
| Kotlin | TreeMap, TreeSet (inherits Java) |
| C# | SortedDictionary<K,V>, SortedSet<T> (Red-Black Tree) |
| Python | No native BST; sortedcontainers.SortedList if allowed |
| Go | No built-in ordered set; most candidates skip or reach for a third-party package |
| JS / TS | No built-in BST; use arrays with manual sorting for most interview problems |
In practice, interview problems hand you a TreeNode struct and expect recursion. You rarely instantiate a BST library. Ordered maps come up when you need floor/ceiling queries or a sorted dynamic set mid-problem.
Four Bugs That End Interviews
BST validation checks only the parent. Already covered. Pass bounds, not just the parent's value. This one has a body count.
Confusing height and depth. Height is measured downward from a node to its furthest leaf. Depth is measured upward from a node to the root. Both are real concepts. Know which one the problem is asking for before you write a single line. Getting this backwards mid-solution and trying to fix it in real time is painful to watch.
Off-by-one in height. A null pointer returns -1 so that a leaf node returns 1 + max(-1, -1) = 0, which is correct. If your base case returns 0 for null, every height in your solution is inflated by one. Pick a convention, state it out loud, and stick to it.
Path sum spanning both directions. In maximum path sum problems, the optimal path can pass through any node going left and right simultaneously. But a path cannot extend upward from both sides. Compute left + node.val + right locally to update a global maximum, then return node.val + max(left, right, 0) upward. Getting this wrong is one of the more demoralizing interview moments because the correct version is two lines away and you can see it but can't quite reach it.
Before your interview, it helps to actually say this stuff out loud under pressure. SpaceComplexity runs on-demand voice mock interviews with rubric-based feedback, so you can find out whether you explain BST validation clearly or just recognize it on paper. Most candidates discover the gap matters more than they expected.