Trees

Nodes that branch instead of chain — an ordering invariant, and recursion as the native tool for almost everything

Nodes brancheach node up to two children — left and right
Ordering invariantleft smaller, right larger — against every ancestor
Recursion-nativeevery operation splits into left/right subproblems
O(log n), if balanceda plain BST offers no guarantee — an unbalanced one is O(n)

1.Binary tree

A binary tree is a tree where every node has AT MOST two children, conventionally called left and right — there is no ordering rule between them, unlike a binary search tree.

Key features

A node with zero children is a leaf; a node with exactly one child is common and perfectly valid — a binary tree is not required to be "full" or "complete"
Building one by hand is just nesting TreeNode(value, left, right) calls — the same shape a linked list's Node(value, next) nesting takes
Almost every binary-tree function has the same skeleton: handle None as the base case, then combine the results of the left and right recursive calls

Every binary-tree function needs a None base case first — a real node always bottoms out at a missing child, and that is exactly where the recursion has to stop instead of dereferencing it.

2.Binary search tree (BST) and its ordering invariant

A BST is a binary tree with one extra rule: for every node, everything in its LEFT subtree is smaller, and everything in its RIGHT subtree is larger — not just its immediate children, the ENTIRE subtree.

Key features

This ordering rule is what makes an inorder traversal of a BST produce values in sorted order, with no sorting step needed
The invariant assumes no duplicate values by default — if duplicates are allowed, a convention (equal goes left, or right) has to be decided and applied consistently
A BST's shape depends entirely on insertion order — the same set of values, inserted in a different order, produces a different (though still valid) tree

Left subtree entirely smaller, right subtree entirely larger — against every ancestor, not just the immediate parent. Inorder traversal is the invariant made visible: it always comes out sorted.

3.Balanced vs unbalanced trees (why balance matters for complexity)

A balanced tree keeps its height close to log2(n) for n nodes, so search/insert/delete stay O(log n). An unbalanced tree can degrade toward a straight line — height n — making the same operations O(n), no better than a linked list.

Key features

Height of a perfectly balanced tree with n nodes is about log2(n); height of a maximally unbalanced tree is n - 1
Self-balancing trees (AVL, red-black) automatically restructure on insert/delete to keep height near log2(n) — out of scope at this level, but this exact problem is the reason they exist
A plain BST offers no balance guarantee at all — worst-case O(n) operations are a real risk, not a theoretical one, if input arrives sorted or nearly sorted

Balance is about shape, not values — the same values inserted in a different order can turn an O(log n) tree into an O(n) chain, and a plain BST does nothing to stop it.

4.BST insert, search, delete

Insert and search both use the ordering invariant to pick a direction at every node — smaller goes left, larger goes right — until they hit the target or an empty spot. Delete is the same idea, plus three cases for what to do once the node to remove is actually found.

Key features

insert and delete both return the (possibly new) root of the subtree they were called on — every recursive call must be captured with node.left = insert(node.left, value), not called and discarded
Deleting a two-children node never actually removes that node object — it copies the successor's VALUE into it, then deletes the successor (which has at most one child) from its original position
All three operations are O(height) — O(log n) on a balanced tree, but O(n) on a degenerate one, exactly the balance trade-off the previous concept describes

Insert and search both follow the ordering invariant down to a None or a match; delete additionally has to relink around whatever it removes — always reassign a recursive call's return value, never call it and discard it.

5.Validating a BST

The naive instinct — compare each node only to its immediate children — misses violations buried deeper in the tree. The correct approach carries a valid (low, high) range down through the recursion, so every node is checked against ALL of its ancestors, not just its direct parent.

Key features

The root starts with an unbounded range, (-infinity, infinity) — every constraint after that comes from an ancestor's value
A node checked only against its immediate parent can pass that local check while still violating the invariant against a grandparent or the root — see algorithms.trees.bst-ordering-invariant for exactly this shape of tree
The range-based check runs in O(n), visiting each node once — the same cost as any other traversal

Carry a (low, high) range down through the recursion, tightened by every ancestor along the way — checking only the immediate parent is the single most common way to ship a broken BST validator.

6.Lowest common ancestor (BST and general binary tree versions)

The lowest common ancestor (LCA) of two nodes is the deepest node that has both of them somewhere in its subtree — possibly being one of the two targets itself.

Key features

On a BST specifically, the ordering invariant gives a shortcut: walk down from the root, and the first node where p and q split to different sides (or equal the node itself) IS the LCA — no need to search both subtrees
"Lowest" means deepest, not smallest value — the LCA is the ancestor FARTHEST from the root that still has both targets underneath it
The general version has no invariant to lean on, so it must actually search both subtrees and combine the results — O(n) worst case, versus O(height) for the BST-optimized version

If a node's left search and right search each find one target, that node is the LCA. On a BST, skip the search entirely — the invariant tells you which direction to go at every step.

7.Computing height/depth

height is measured DOWN from a node to its farthest leaf; depth is measured UP from a node to the root. A recursive height function is bottom-up — it needs both children's answers before it can compute its own. Finding a specific node's depth is top-down — a search from the root, counting steps as it descends.

Key features

height(None) = -1 is the convention used here, so a single leaf correctly comes out to height 0 (1 + max(-1, -1))
A node's own depth requires knowing the path from the root — there is no shortcut without either a parent pointer or a top-down search
height(root) and the tree's overall height are the same number — height is always described relative to some starting node, and the root is just one particular choice of node

height looks down and combines both children's answers; depth looks up (implemented as a top-down search from the root) and stops the moment it finds the target.

8.Diameter of a binary tree

The diameter is the longest path between any two nodes, measured in edges — and that path does not have to pass through the root.

Key features

A naive approach — recompute height from scratch at every node — costs O(n²); tracking the best answer inside the same recursion that computes height brings it down to O(n)
The overall diameter does not have to touch the root at all — it is whichever node's own left-height + right-height + 2 turns out largest
A single node has diameter 0 (no path), matching left-height and right-height of -1 each: -1 + -1 + 2 = 0

Track the best left-height + right-height + 2 seen at ANY node while computing height in one pass — the longest path does not have to run through the root.

9.Checking if a tree is balanced

A tree is height-balanced if, at EVERY node, the heights of its left and right subtrees differ by at most 1 — not just at the root.

Key features

A tree can have a balanced ROOT (its two top-level subtrees are close in height) while still being unbalanced deeper down — the check has to hold at every node, which is exactly why it is computed bottom-up
-1 does double duty here: it is both this function's own convention for 'empty subtree height' at the leaves and the sentinel that means 'unbalanced, stop checking' once propagated upward
This is O(n) total — each node is visited once, and an unbalanced result short-circuits every ancestor above the failure without recomputing anything

Balance must hold at EVERY node, not just the root — compute height bottom-up and short-circuit to a sentinel the instant any node fails, instead of recomputing height from scratch at each one.

Spotted a mistake on this page? Tell us.

Read Sheet