Trees and Binary Search Trees
Hierarchical data, the four classic traversals, and how a binary search tree gives ordered search, insert and delete in O(h) time.
intermediate50 min#trees#bst#traversal#recursion
Prerequisites: Recursion, Stacks and Queues
Why it matters
Trees model anything with a parent and children: file systems, the HTML DOM, org charts, expression parsers, and the decision structure inside many algorithms. A binary search tree (BST) adds an ordering rule that lets you search, insert and delete in time proportional to the tree's height, and it keeps data sorted as a side effect. Databases and language libraries use balanced relatives of it (B-trees, red-black trees) every day, and tree problems are among the most common interview questions.
Intuition
A tree is a family tree turned upside down: one root at the top, and every node has zero or more children. A node with no children is a leaf. The height is the number of nodes on the longest root-to-leaf path (some books count edges instead, so always state which you use).
In a binary tree each node has at most two children, called left and right. A BST adds one rule: for every node, all keys in its left subtree are smaller and all keys in its right subtree are larger. That is exactly the rule of the "guess my number" game. At each node you compare once and throw away one whole side.
50
/ \
30 70
/ \ / \
20 40 60 80
/
35
Searching for 35 visits 50, 30, 40, 35: four comparisons instead of scanning eight keys.
How it works
Traversals visit every node exactly once. They differ only in when you handle the node relative to its children:
- Pre-order (node, left, right): copy a tree, serialize it.
- In-order (left, node, right): on a BST this yields keys in sorted order.
- Post-order (left, right, node): children before parents, ideal for deleting a tree or computing sizes and heights.
- Level-order (breadth first): row by row using a queue.
The first three are naturally recursive and use stack space proportional to the height. Level-order replaces recursion with a queue.
In-order traversal on the example BST. Green is the node being visited, amber is already visited. Notice that the output comes out sorted.
The other orders walk the same tree and only change when the node is handled, so the root lands in a different place in each output.
Insert walks down comparing keys until it falls off the tree, then attaches a new leaf there. Search is the same walk. Delete has three cases:
- The node is a leaf: remove it.
- The node has one child: replace the node with that child.
- The node has two children: copy in the in-order successor (smallest key in the right subtree), then delete that successor from the right subtree. The successor has no left child, so its removal falls into case 1 or 2.
Search and insert are the same downward walk: amber is the path taken so far, green is the current node. Insert just attaches a leaf where the search would have failed.
Balance. Every cost above is O(h). If keys arrive in sorted order, each insert goes right and the tree degrades into a linked list with h equal to n. A self-balancing tree (AVL, red-black) rotates nodes after updates to keep h near log n. You rarely write one by hand, but you should know why they exist.
Same five keys, two insertion orders. The shape, not the key count, decides the cost.
| Operation | Time | Notes |
|---|---|---|
| Search / insert / delete (balanced BST) | O(log n) | Height is about log n |
| Search / insert / delete (worst case, skewed) | O(n) | Sorted inserts make a chain |
| Any traversal | O(n) | Each node visited once |
| Extra space for recursive traversal | O(h) | Call stack depth |
| Min / max | O(h) | Walk all the way left or right |
Code: a BST with all four traversals
import json
from collections import deque
def show(*xs):
print(*(json.dumps(x, separators=(',', ':')) for x in xs))
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def insert(root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
elif key > root.key:
root.right = insert(root.right, key)
return root
def search(root, key):
while root and root.key != key:
root = root.left if key < root.key else root.right
return root is not None
def delete(root, key):
if root is None:
return None
if key < root.key:
root.left = delete(root.left, key)
elif key > root.key:
root.right = delete(root.right, key)
else:
if root.left is None:
return root.right
if root.right is None:
return root.left
succ = root.right
while succ.left:
succ = succ.left
root.key = succ.key
root.right = delete(root.right, succ.key)
return root
def inorder(n):
return inorder(n.left) + [n.key] + inorder(n.right) if n else []
def preorder(n):
return [n.key] + preorder(n.left) + preorder(n.right) if n else []
def postorder(n):
return postorder(n.left) + postorder(n.right) + [n.key] if n else []
def level_order(root):
out, q = [], deque([root] if root else [])
while q:
level = []
for _ in range(len(q)):
n = q.popleft()
level.append(n.key)
if n.left: q.append(n.left)
if n.right: q.append(n.right)
out.append(level)
return out
def height(n):
return 0 if n is None else 1 + max(height(n.left), height(n.right))
root = None
for k in [50, 30, 70, 20, 40, 60, 80, 35]:
root = insert(root, k)
show(inorder(root))
show(preorder(root))
show(postorder(root))
show(level_order(root))
show(search(root, 60), search(root, 65), height(root))
root = delete(root, 30)
show(inorder(root), root.left.key)
root = None
for k in range(1, 6):
root = insert(root, k)
show(height(root))class Node {
constructor(key) {
this.key = key;
this.left = null;
this.right = null;
}
}
function insert(root, key) {
if (root === null) return new Node(key);
if (key < root.key) root.left = insert(root.left, key);
else if (key > root.key) root.right = insert(root.right, key);
return root;
}
function search(root, key) {
while (root !== null && root.key !== key) {
root = key < root.key ? root.left : root.right;
}
return root !== null;
}
function remove(root, key) {
if (root === null) return null;
if (key < root.key) root.left = remove(root.left, key);
else if (key > root.key) root.right = remove(root.right, key);
else {
if (root.left === null) return root.right;
if (root.right === null) return root.left;
let succ = root.right;
while (succ.left) succ = succ.left;
root.key = succ.key;
root.right = remove(root.right, succ.key);
}
return root;
}
const inorder = (n) => (n ? [...inorder(n.left), n.key, ...inorder(n.right)] : []);
const preorder = (n) => (n ? [n.key, ...preorder(n.left), ...preorder(n.right)] : []);
const postorder = (n) => (n ? [...postorder(n.left), ...postorder(n.right), n.key] : []);
function levelOrder(root) {
const out = [];
let queue = root ? [root] : [];
while (queue.length) {
out.push(queue.map((n) => n.key));
const next = [];
for (const n of queue) {
if (n.left) next.push(n.left);
if (n.right) next.push(n.right);
}
queue = next;
}
return out;
}
const height = (n) => (n === null ? 0 : 1 + Math.max(height(n.left), height(n.right)));
let root = null;
for (const k of [50, 30, 70, 20, 40, 60, 80, 35]) root = insert(root, k);
console.log(JSON.stringify(inorder(root)));
console.log(JSON.stringify(preorder(root)));
console.log(JSON.stringify(postorder(root)));
console.log(JSON.stringify(levelOrder(root)));
console.log(search(root, 60), search(root, 65), height(root));
root = remove(root, 30);
console.log(JSON.stringify(inorder(root)), root.left.key);
root = null;
for (let k = 1; k <= 5; k++) root = insert(root, k);
console.log(height(root));Python prints:
[20,30,35,40,50,60,70,80]
[50,30,20,40,35,70,60,80]
[20,35,40,30,60,80,70,50]
[[50],[30,70],[20,40,60,80],[35]]
true false 4
[20,35,40,50,60,70,80] 35
5
JavaScript prints exactly the same seven lines. The in-order output is sorted, deleting 30 (two children) pulls up its successor 35, and inserting 1 to 5 in order produces height 5, a chain.
Common pitfalls
- Forgetting the base case: a function that dereferences
node.leftwithout checking for an empty tree crashes on every leaf. - Validating a BST locally: checking only
left < node < rightfor each node is wrong. A key deep in the left subtree can still exceed an ancestor. Pass down min and max bounds, or check that the in-order output is strictly increasing. - Assuming a BST is balanced: inserting sorted data silently produces O(n) operations. Shuffle input or use a self-balancing structure.
- Mixing up height and depth: depth counts down from the root, height counts up from the leaves.
- Deep recursion: a skewed tree with a million nodes overflows the call stack in both Python and JavaScript. Use an explicit stack for that case.
- Duplicates: decide up front whether they are rejected, counted, or sent to one side. The code above ignores them.
Practice
Maximum depth of a binary tree easy
Hint
Height of a tree in terms of the heights of its subtrees.
Show solution
The height of an empty tree is 0. Otherwise it is 1 plus the larger of the left and right heights. This is a post-order computation, O(n) time and O(h) stack space.
Validate a binary search tree medium
Hint
A node's valid range is narrowed by every ancestor, not just its parent.
Show solution
Recurse with an allowed open interval (lo, hi), starting at (negative infinity, positive infinity). A node is valid if lo is less than its key and its key is less than hi. Go left with (lo, key) and right with (key, hi). O(n) time. The in-order alternative: traverse and confirm each key is greater than the previous one.
Lowest common ancestor in a BST medium
Hint
Compare both targets with the current node and use the BST ordering.
Show solution
Start at the root. If both targets are smaller than the node, go left; if both are larger, go right; otherwise the current node is the split point and is the answer. Iterative, O(h) time, O(1) space.
Level-order grouped by depth, then zigzag hard
Hint
Process one level per loop iteration, using the queue length at the start of the level.
Show solution
Do the level-order traversal from the code above, which already returns a list per level. For zigzag, reverse every odd-numbered level before appending it. The queue holds at most one level plus children, so space is O(width) and time is O(n).
Interview questions
- Which traversal gives sorted output from a BST, and why? In-order, because it visits the smaller left subtree, then the node, then the larger right subtree at every level.
- What is the cost of search in a BST? O(h): O(log n) if balanced, O(n) if skewed.
- How do you delete a node with two children? Replace its key with the in-order successor (or predecessor) and delete that node, which has at most one child.
- Why do self-balancing trees exist? To guarantee h stays near log n regardless of insertion order, via rotations.
- Recursive versus iterative traversal? Recursion is shorter; an explicit stack avoids stack overflow on very deep trees.
Interviewers look for: clarity about whether the tree is a BST or just a binary tree, handling the empty tree, naming the complexity in terms of height, and awareness that balance is not free.
Quick check
You insert the keys 1, 2, 3, 4, 5, 6 in that order into an empty plain BST. What is the cost of searching for 6?
Finished this lesson?
Further resources
- Tree traversal (Wikipedia) (article)
- Binary search tree (Wikipedia) (article)
- Self-balancing binary search tree (Wikipedia) (article)