Trees
dsa.fetehadin.com4.1 Binary Trees & Tree Terms
Root, parent, child, leaf, sibling, depth, height, level, subtree; full, complete and perfect binary trees; and the Node struct with recursive count and height.
| count nodes / leaves | O(n): visits every node once |
| height | O(n) |
| find a value (no ordering) | O(n) |
| Space | O(h) recursion stack, where h is the height |
- ✗Mixing up depth (from the root down to a node) and height (from a node down to its deepest leaf).
- ✗Not stating your height convention. Here, a single node has height 0 and an empty tree −1. Some books count nodes instead of edges.
- ✗Thinking "complete" and "full" mean the same thing.
4.2 Tree Traversals
Preorder, inorder and postorder (depth-first, recursive) and level order (breadth-first, with a queue). Know them by hand and in code.
| pre / in / post order | O(n): every node once |
| level order | O(n) |
| Space | O(h) recursion for DFS; O(w) queue for level order (w = widest level) |
- ✗Mixing the orders. Remember where the Node goes - pre = N L R, in = L N R, post = L R N.
- ✗Forgetting that "left before right" is the same in all three.
- ✗Using a stack for level order (that gives a DFS order instead).
4.3 Binary Search Tree
Left is smaller, right is bigger. Insert, search, find min and max by walking one path, and why the tree's shape decides whether that is O(log n) or O(n).
| search / insert, balanced | O(log n) |
| search / insert, skewed | O(n) |
| min / max | O(h) |
| inorder (sorted output) | O(n) |
| Space | O(n) for the nodes, O(h) recursion |
- ✗Writing
insert(root->left, x);without assigning the result back toroot->left. - ✗Checking only a node's children, not the whole subtree, when asked "is this a BST?".
- ✗Forgetting the
nullptrcheck before readingroot->data.
4.4 BST Delete (3 Cases)
Deleting a leaf, a node with one child, and a node with two children by copying the inorder successor. The most-asked BST exam question.
| delete, balanced | O(log n) |
| delete, skewed | O(n) |
| Space | O(h) recursion |
- ✗Case 3: copying the successor value but forgetting to delete the successor node itself (you get a duplicate).
- ✗Case 3: searching for the successor in the left subtree. Successor = min of the right subtree.
- ✗Not returning the new subtree root, so the parent still points at the deleted node.
4.5 Heap Sort
Build a max-heap in the array, then repeatedly swap the root (the largest item) to the end and sift down. O(n log n) in every case, in-place.
| Build heap | O(n) |
| Each extract-max (swap + heapify) | O(log n) |
| Best / average / worst | O(n log n) |
| Space | O(1) iterative, O(log n) with recursive heapify |
| Stable · in-place | no · yes |
- ✗Using 1-based formulas (2i, 2i+1) with a 0-based array. With 0-based it is 2i+1 and 2i+2.
- ✗Starting the build loop at i = 0 instead of n/2 − 1, going down to 0.
- ✗Calling heapify on the whole array instead of the shrinking heap size
end.
4.6 General Trees (Left-Child, Right-Sibling)
Trees where a node can have any number of children, stored with only two pointers per node using the left-child/right-sibling representation.
| visit all nodes | O(n) |
| find the k-th child | O(k) |
| count the children of a node | O(degree) |
| Space | O(n), exactly two pointers per node |
- ✗Linking a node's second child to the parent instead of to the first child's
nextSibling. - ✗Drawing siblings as "right child of the parent".
- ✗Forgetting that the root has no siblings.
- Binary tree:
- A tree in which every node has at most two children, left and right.
- Root / leaf:
- The top node (no parent) / a node with no children.
- Depth / height:
- Depth: edges from the root down to a node. Height: edges from a node down to its deepest leaf.
- Full / complete / perfect:
- Full: 0 or 2 children everywhere. Complete: all levels full except the last, filled from the left. Perfect: all levels full.
- BST:
- Binary search tree: for every node, left subtree < node < right subtree.
- Inorder successor:
- The next value in sorted order; for a node with a right child, the minimum of its right subtree.
- Preorder / inorder / postorder:
- Depth-first traversals: Node-Left-Right / Left-Node-Right / Left-Right-Node.
- Level-order traversal:
- Visit a tree level by level using a queue (BFS on a tree).
- General tree:
- A tree whose nodes may have any number of children.
- Left-child, right-sibling:
- Stores a general tree with two pointers per node: first child and next sibling.
- Max-heap:
- A complete binary tree where every parent is ≥ its children; stored in an array.
- Heapify:
- Sift a node down until the heap property holds below it. O(log n).