Quick Overview
Pre-, in- and post-order differ only in when a node is read relative to its children, and all three visit every node once in `O(N)`. In-order on a BST emits the values already sorted; the other two cannot.
Traversing a tree means visiting every node once in a deterministic order. Depth-First Search (DFS) explores down a branch as deep as possible before backtracking.
The name specifies WHEN the current root node is processed relative to its left and right subtrees:
4
/ \
2 5
/ \
1 3
Pre-order: [ 4, 2, 1, 3, 5 ]
In-order: [ 1, 2, 3, 4, 5 ] ◄── Sorted order on BST!
Post-order: [ 1, 3, 2, 5, 4 ]
// In-order Traversal: Left -> Node -> Right
function inOrderTraversal(root, result = []) {
if (!root) return result;
inOrderTraversal(root.left, result); // 1. Traverse left subtree
result.push(root.val); // 2. Visit current node
inOrderTraversal(root.right, result); // 3. Traverse right subtree
return result;
}
// Pre-order Traversal: Node -> Left -> Right
function preOrderTraversal(root, result = []) {
if (!root) return result;
result.push(root.val);
preOrderTraversal(root.left, result);
preOrderTraversal(root.right, result);
return result;
}
O(N) where N is total nodes (every node visited once).O(H) where H is tree height (call stack depth).K-th smallest element in a BST, an in-order traversal yields elements in sorted order directly without sorting!Use in-order for BST validation. Next, let's explore Breadth-First Search (BFS) Level-Order Traversal!
Big O describes how work grows, not how long it takes. An `O(N^2)` algorithm on 1,000 items does a million steps; the same work at `O(N log N)` does about 10,000.
A dynamic array doubles rather than growing by one, so the expensive copy lands on the 1st, 2nd, 4th and 8th push. Averaged across every push, that is `O(1)` amortised.
A nested loop tests every pair in `O(N^2)`. On sorted data, moving two pointers inward from both ends rules out half the remaining candidates at each step and settles it in one `O(N)` pass.