Trees

Binary trees

• A tree is a connected graph with no cycles; each node has one parent (except the root). A binary tree allows at most two children per node (left, right).
• Trees and graphs are the same idea, except a tree has no cycles, so no visited set is needed when walking down from the root. For general graphs you must track visited nodes (see Graphs).
• Height of a balanced tree is $O(\log n)$; a degenerate (skewed) tree has height $O(n)$. Recursive traversals use $O(h)$ stack space.
• Recognition signals: “root”, “children”, “subtree”, “ancestor”, “level”, “depth/height”, hierarchical data.

Binary search tree (BST)

• Every value in a node’s left subtree is less than the node’s value, and every value in the right subtree is greater (duplicates are allowed on one fixed side, or disallowed, depending on the problem).
• Search, insert and remove are $O(h)$: $O(\log n)$ when balanced, $O(n)$ when skewed (for example, inserting sorted data).
• Inorder traversal of a BST visits values in ascending order in $O(n)$. This solves “kth smallest”, “validate BST” and “BST iterator” problems.
• Removing a node with two children: replace it with the smallest node of the right subtree (or the largest of the left), then remove that node.
• Gotcha: validate a BST by passing down (low, high) bounds, not by only comparing a node with its children.

See BST search and BST insert and remove.

Traversals

For a tree with root 1, left child 2 (children 4, 5) and right child 3:

• All traversals run in $O(n)$ time.
• DFS uses $O(h)$ extra space. BFS uses $O(w)$, where $w$ is the maximum width of the tree (up to about $n/2$).
• DFS can be recursive or iterative with an explicit stack; see Iterative DFS.
• For BFS, take len(queue) at the start of each loop iteration to process exactly one level at a time.

See DFS and BFS.

DFS vs BFS

Both algorithms have the same time complexity; neither is generally faster. Choose by the question being asked, not by speed.

Self-balancing trees

AVL tree

• A BST that stays height-balanced: for every node, the balance factor $height(left) - height(right)$ is -1, 0 or 1.
• Insert and delete work like a BST, followed by rotations to restore balance. Search, insert and delete are $O(\log n)$.
• Four cases: left-left (right rotation), right-right (left rotation), left-right (left rotation on the child, then right rotation) and right-left (right rotation on the child, then left rotation).
• More strictly balanced than a red-black tree, so lookups are faster but updates do more rotations. Good for read-heavy in-memory sets, dictionaries and database lookups.

Red-black tree

• A self-balancing BST where each node is red or black.
• Properties:
  • The root is black.
  • A red node has no red child (no two adjacent red nodes).
  • Every path from a node to its descendant null leaves has the same number of black nodes.
  • Null leaves count as black.
• These rules guarantee that the longest path is at most twice the shortest, so the height is $O(\log n)$ and search, insert and delete are $O(\log n)$.
• Fewer rotations on insert and delete than AVL; commonly used to implement ordered maps and sets in standard libraries.

B-tree

• A multiway search tree designed for disk access: each node holds many sorted keys, so the tree is very shallow and each node read fetches a whole disk block.
• Defined by a minimum degree $t$ (chosen from the disk block size):
  • Every non-root node has at least $t - 1$ keys; every node has at most $2t - 1$ keys; the root has at least one key.
  • A node with $k$ keys has $k + 1$ children, and the child between keys $k_1$ and $k_2$ holds the keys between them.
  • All leaves are at the same depth.
  • It grows and shrinks at the root (by splitting and merging nodes), not at the leaves.
• Search, insert and delete are $O(\log n)$. Used in database indexes and file systems.

You will rarely implement these in an interview; know the properties and why they exist (guaranteed $O(\log n)$ height).

Other tree structures

• Trie (prefix tree): per-character children, for prefix search and word dictionaries. See Trie.
• Segment tree: range queries (sum, min, max) with point or range updates in $O(\log n)$. See Segment Tree.
• Heap: a complete binary tree stored in an array. See Heaps.
• Union-Find is a forest of parent pointers, covered in Graphs.

Templates

• BST search: searching a BST by value.
• BST insert and remove: insert a value and remove a node, including the two-children case.
• DFS: recursive inorder, preorder and postorder traversals.
• Iterative DFS: inorder, preorder and postorder using an explicit stack.
• BFS: level order traversal with a queue.
• Segment Tree: build, point update and range query.
• Trie: insert, search and prefix search.

Problems