A tree is what you get when a linked list stops being a single chain and lets each node point to more than one "next" — a filesystem's folders, an org chart, the DOM of a web page, the decision tree behind a chess engine's search. A binary search tree (BST) is the specific shape that makes trees interesting for interviews: it adds an ordering rule to a binary tree so that searching, inserting and deleting can all be done in roughly the same time a binary search takes on a sorted array, but without the O(n) cost of shifting elements. Interviewers reach for trees constantly because a huge slice of real systems are trees underneath — a database B-tree index, a filesystem directory structure, a compiler's parse tree — and because BSTs are the cleanest vehicle for teaching recursion, invariants and the balance-vs-degradation trade-off that shows up again in heaps, tries and self-balancing structures.
This page assumes you already understand recursion and Big-O from the complexity page. The goal here is to build the mental model precisely enough that you can reconstruct any traversal or operation from first principles in an interview, rather than recalling memorized code.
Depth and height are measured in opposite directions and people mix them up constantly. Depth answers "how far down am I from the root" and is a property of one specific node, counted top-down. Height answers "how far down does it go from here" and is a property of a subtree, counted bottom-up from the deepest leaf. The height of the whole tree is, by definition, the depth of its deepest leaf — which is why "the height of the tree" and "the maximum depth of any node in the tree" are the same number even though depth and height are computed by walking in opposite directions.
A subtree is just "the tree you get by picking any node and treating it as a new root" — this is the property that makes recursion the natural tool for trees: almost every tree algorithm is "do something with this node, then recurse on its left subtree, then recurse on its right subtree", because each subtree is a smaller instance of the exact same problem.
def insert(root, val):
if root is None:
return Node(val)
if val < root.val:
root.left = insert(root.left, val)
elif val > root.val:
root.right = insert(root.right, val)
return rootNone) is where the new value belongs: create the node and return it so the parent can link to it.root unchanged so every level of the recursion re-links the same tree. Cost: one node per level, O(height).A plain binary tree tells you nothing about where a value could be — finding it means checking every node, O(n). The BST invariant turns every node into a decision point: because the invariant holds at every node (not just the root), one comparison at the root doesn't just rule out that node, it rules out an entire subtree of values at once. That's the same trick binary search on a sorted array uses — halve the remaining search space each step — except a BST doesn't need contiguous memory to do it, so insertion and deletion don't require shifting anything. Insert works by walking the same path search would take until you fall off the tree (hit None), then attaching the new node there — the invariant is automatically preserved because you only ever attach where the invariant says the value belongs. Deletion is the fiddly one: deleting a leaf is trivial, deleting a node with one child means splicing the child up, and deleting a node with two children means replacing its value with its inorder successor (the smallest value in its right subtree) and deleting that successor instead, which is guaranteed to have at most one child.
This is the point that gets glossed over and then asked about directly: a BST's O(log n) claim depends entirely on the tree being roughly balanced — every node's left and right subtrees holding a similar number of nodes. Nothing in the plain BST insert algorithm enforces that. If you insert already-sorted data, every new value is larger than everything before it, so it always attaches as a right child of the current rightmost node, and you've built a glorified linked list with tree syntax: height n instead of height log2(n), and every operation degrades to O(n) because there's no branching left to exploit. The demo above shows it concretely — 7 nodes, same values, height 2 versus height 6, purely a function of insertion order.
Self-balancing trees exist specifically to close this gap: AVL trees rebalance via rotations after every insert/delete to keep the two subtrees' heights within 1 of each other, guaranteeing O(log n) always; red-black trees use a looser color-based balancing rule that rebalances less aggressively (cheaper writes, slightly less tight balance) and is what most standard-library ordered maps (Java's TreeMap, C++'s std::map) actually use internally. You are not expected to implement rotations from memory in most interviews, but you are expected to know the plain-BST guarantee is conditional on balance, and to name AVL/red-black trees as the fix.
def inorder(node, out):
if node is None: return
inorder(node.left, out)
out.append(node.val)
inorder(node.right, out)append line above both calls for preorder, or below both for postorder; nothing else changes. Each node is visited once: O(n) time, O(height) stack.All three are the same recursive walk with the "visit" step moved to a different position, and that one position decides what the traversal is useful for. Inorder visits left, then the node, then right — on a BST that means you always finish an entire smaller subtree before looking at the current node and an entire larger subtree after it, which is exactly why inorder traversal of a BST produces sorted output: it's visiting "everything smaller", "this value", "everything bigger", recursively, and that pattern composes into a global sort for free. Preorder visits the node before either subtree, so it always outputs a parent before its children — useful for reconstructing the same tree shape elsewhere (write preorder out, read it back in, reinsert in that order, and you rebuild an equivalent BST) or for a quick structural copy. Postorder visits a node only after both subtrees are fully done, which is the only order where you can safely free/delete a node without losing access to its children first, and it's the natural order for evaluating an expression tree bottom-up (evaluate both operands, then apply the operator at the parent).
def level_order(root):
if root is None: return []
out, q = [], deque([root])
while q:
node = q.popleft()
out.append(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
return outdeque gives O(1) pops from the front; list.pop(0) would be O(n).The three DFS orders all go deep before they go wide — they commit to one child's entire subtree before even looking at the sibling. Level-order does the opposite: visit everything at depth 0, then everything at depth 1, then depth 2. Recursion's call stack naturally models "go deep and come back", so DFS falls out of plain recursion for free; it cannot model "hold several partially-explored branches at the same depth and interleave between them", which is exactly what level order needs. A FIFO queue does that job directly: pop a node, visit it, push its children onto the back — since children go in behind everything already queued at earlier depths, the queue enforces that an entire depth is fully drained before the next depth starts.
def diameter(root):
best = [0]
def dfs(node):
if node is None: return -1
lh, rh = dfs(node.left), dfs(node.right)
best[0] = max(best[0], lh + rh + 2)
return 1 + max(lh, rh)
dfs(root)
return best[0]dfs returns a node's height. An empty subtree returns −1, so a leaf gets 1 + max(−1, −1) = 0.lh + 1 edges plus rh + 1 edges. Keep the best seen anywhere, because the diameter need not pass through the root.def lca(root, a, b):
node = root
while node:
if a < node.val and b < node.val: node = node.left
elif a > node.val and b > node.val: node = node.right
else: return node.valDiameter looks like it should need checking every pair of nodes, but the longest path between any two nodes always passes through some single node as its highest point, and at that node the path length is exactly the height of its left subtree plus the height of its right subtree plus 2 (one edge down each side). So a single postorder pass that returns each subtree's height while updating a running best answer at every node finds the diameter in one O(n) traversal, without ever explicitly enumerating pairs.
LCA (lowest common ancestor) asks "what's the deepest node that has both A and B somewhere below it (or is one of them)". On a plain binary tree you'd need to find both root-to-node paths and compare them. A BST's ordering invariant makes this much cheaper: starting at the root, if both targets are smaller than the current node, the LCA must be in the left subtree (the current node can't be an ancestor of a split, it's above both); if both are larger, it must be in the right subtree; the first node where they "split" — one is not greater than it and the other is not less — is the LCA, because that's the deepest point where their paths still overlap. That gives an O(h) walk down the tree, no path-storing required.
None), v isn't present.None, then attach a new node with value v at that exact spot — the invariant holds automatically because that's the only place v is allowed to go.A BST with insert, all three DFS orders, level order via a queue, height, diameter and LCA — then a direct comparison of a balanced vs. a skewed insertion order on the same 7 values.
from collections import deque
class Node:
__slots__ = ("val", "left", "right")
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def insert(root, val):
if root is None:
return Node(val)
if val < root.val:
root.left = insert(root.left, val)
elif val > root.val:
root.right = insert(root.right, val)
return root
def build(values):
root = None
for v in values:
root = insert(root, v)
return root
def inorder(node, out):
if node is None: return
inorder(node.left, out); out.append(node.val); inorder(node.right, out)
def preorder(node, out):
if node is None: return
out.append(node.val); preorder(node.left, out); preorder(node.right, out)
def postorder(node, out):
if node is None: return
postorder(node.left, out); postorder(node.right, out); out.append(node.val)
def level_order(root):
if root is None: return []
out, q = [], deque([root])
while q:
node = q.popleft()
out.append(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
return out
def height(node):
if node is None: return -1
return 1 + max(height(node.left), height(node.right))
def diameter(root):
best = [0]
def dfs(node):
if node is None: return -1
lh, rh = dfs(node.left), dfs(node.right)
best[0] = max(best[0], lh + rh + 2)
return 1 + max(lh, rh)
dfs(root)
return best[0]
def lca(root, a, b):
node = root
while node:
if a < node.val and b < node.val: node = node.left
elif a > node.val and b > node.val: node = node.right
else: return node.val
return None
values = [50, 30, 70, 20, 40, 60, 80]
root = build(values)
io, pre, post = [], [], []
inorder(root, io); preorder(root, pre); postorder(root, post)
print("insert order :", values)
print("inorder :", io)
print("preorder :", pre)
print("postorder :", post)
print("level order :", level_order(root))
print("height(root) :", height(root))
print("diameter :", diameter(root))
print("lca(20, 40) :", lca(root, 20, 40))
print("lca(20, 80) :", lca(root, 20, 80))
print("lca(60, 80) :", lca(root, 60, 80))
skewed = build([10, 20, 30, 40, 50, 60, 70])
print("skewed height :", height(skewed), " (7 nodes, inserted sorted)")
print("balanced height:", height(root), " (7 nodes, inserted mid-first)")
# Output:
# insert order : [50, 30, 70, 20, 40, 60, 80]
# inorder : [20, 30, 40, 50, 60, 70, 80]
# preorder : [50, 30, 20, 40, 70, 60, 80]
# postorder : [20, 40, 30, 60, 80, 70, 50]
# level order : [50, 30, 70, 20, 40, 60, 80]
# height(root) : 2
# diameter : 4
# lca(20, 40) : 30
# lca(20, 80) : 50
# lca(60, 80) : 70
# skewed height : 6 (7 nodes, inserted sorted)
# balanced height: 2 (7 nodes, inserted mid-first)Node uses __slots__ to save memory per node; otherwise it is just a value with left/right links.build inserts values one by one with the BST insert. Mid-value first gives the balanced tree from the diagrams.level_order print exactly the orders shown in the figures.height returns −1 for an empty tree, so a single node has height 0 and this tree has height 2.diameter and lca are the functions explained above: diameter 4, LCA(20, 40) = 30, LCA(20, 80) = 50, LCA(60, 80) = 70.Q: What invariant makes something a valid BST?
A: For every node, every value in its left subtree is smaller than the node's value and every value in its right subtree is larger — and this must hold at every node in the tree, not just between a node and its immediate children. Checking only immediate children misses violations further down (e.g. a right-subtree node smaller than an ancestor two levels up), which is a classic "validate a BST" interview bug.
Q: Why does inorder traversal of a BST visit nodes in sorted order?
A: Inorder is "recurse left, visit node, recurse right", and the BST invariant guarantees everything in the left subtree is smaller and everything in the right subtree is larger. So at every node the traversal outputs "everything smaller than this value" (recursively, itself already sorted), then this value, then "everything larger" — that pattern composes recursively into one global ascending sequence.
Q: Why can BST operations degrade from O(log n) to O(n), and what causes it?
A: O(log n) assumes the tree stays roughly balanced, so each comparison eliminates about half the remaining nodes. Nothing in plain insertion enforces balance — inserting data that's already sorted (or reverse-sorted) makes every new node attach as the rightmost (or leftmost) child of the previous one, producing a tree of height n instead of log2(n), i.e. a linked list wearing tree syntax. Self-balancing variants (AVL, red-black) fix this by rebalancing on every insert/delete.
Q: Walk through the three DFS traversal orders on a small tree and say when you'd use each.
A: On root 50 with children 30 and 70: preorder visits 50 first then recurses left then right (root-before-children, good for serializing/rebuilding a tree); inorder visits left subtree, then 50, then right subtree (sorted order on a BST); postorder visits both subtrees before 50 (children-before-parent, safe for deleting a tree bottom-up or evaluating an expression tree). The only difference between them is where "visit the node" sits relative to the two recursive calls.
Q: Why does level-order traversal need a queue instead of recursion?
A: Recursion's call stack models "finish this whole branch, then come back" — it's inherently depth-first. Level order needs to hold several partially-explored branches at the same depth simultaneously and interleave between them, which is exactly what a FIFO queue does: pop a node, visit it, enqueue its children behind everything already queued at earlier depths, so an entire depth drains before the next one starts.
Q: How would you find the height of a binary tree recursively — what's the base case?
A: Height of a node is 1 + the larger of its two children's heights; the base case is an empty subtree (None), which returns -1 so that a single leaf correctly computes to 1 + max(-1, -1) = 0. Picking a base case of 0 for None instead just shifts every height up by one — either is fine as long as you're consistent and say which you're using.
Q: What's the intuition behind finding the lowest common ancestor of two nodes?
A: On a BST, walk down from the root: if both target values are smaller than the current node, the LCA has to be further left (this node is an ancestor of both, but not the lowest one); if both are larger, further right; the moment the two values are on opposite sides (or one equals the current node), you're standing at the exact point their paths diverge, which is the LCA by definition. On a plain (non-BST) binary tree you don't get that ordering shortcut, so the standard approach is a bottom-up recursive search that returns a node once it has found one target in each of its subtrees.
Follow-up: If the interviewer says "no ordering guarantee, this is a plain binary tree, not a BST" — does your LCA approach still work?
A: No — the left/right comparison trick relies entirely on the BST invariant. On a plain binary tree you instead recurse from the root: if the current node is one of the two targets, return it; otherwise search both subtrees, and if both return non-null, the current node is the LCA (targets are in different subtrees); if only one side returns non-null, propagate that result up. This is O(n) instead of O(h) because there's no ordering to prune the search with.
Follow-up: Your BST insert takes an already-sorted stream of a million values. What actually happens, concretely?
A: Each new value is larger than every value already inserted, so it always becomes the right child of the current rightmost node — the tree grows as a single right-leaning chain of height ~1,000,000 instead of ~20. Every subsequent search, insert, or delete then costs O(n) instead of O(log n), and a naive recursive implementation could even blow the call stack. The fix is either to use a self-balancing tree, insert via random shuffling first, or pick a data structure (sorted array with binary search, if inserts are rare) that fits the actual access pattern.
Follow-up: Diameter and height sound similar — could you compute diameter with two separate height() calls per node instead of one combined pass?
A: You could call height() on the left and right subtree separately at every node, but that recomputes height from scratch at every node, giving O(n²) overall (each of n nodes triggers an O(n) height call). The single-postorder-pass version returns height as a byproduct while simultaneously updating the diameter candidate at each node, so height and diameter are computed together in one O(n) traversal — the O(n²) version is the trap, not a valid alternative.
A BST is the right choice when you need ordered data with fast search, insert, delete, and range/successor queries all at once — a sorted array gives you fast search but O(n) insert/delete, and a hash table gives you fast lookup but no ordering at all (no "give me everything between 30 and 70" or "what's the next value after this one"). A plain BST is the wrong choice whenever insertion order isn't random or can be adversarial (sorted input, or an attacker who knows your insert order and wants to degrade you to O(n)) — in that case use a self-balancing tree (AVL for tighter balance and faster reads, red-black for cheaper writes) or, if you don't need per-node structure at all, a B-tree/B+-tree when the data lives on disk and you want to minimize the number of page reads. If you don't need ordering, don't pay for it: a hash table beats a BST on raw average-case lookup speed, and if all you need is "give me the minimum/maximum repeatedly", a heap does that in O(log n) with far less overhead than a full BST.