Binary trees and traversals

Four ways to visit every node. The first thing you do with any tree.

Three depth-first orders — one line moved

• In-order — left, node, right → sorted (for a BST)
• Pre-order — node, left, right → copy / serialize
• Post-order — left, right, node → delete / evaluate
• Level-order — breadth-first, with a queue → nearest-first

Watch in-order produce sorted output

Dive left to 1, work rightward and up: 1,3,4,5,7,8,9. Sorted, for free.

Cost

• Every traversal: O(n) time (each node once)
• Space: O(h) — recursion stack or queue
• Balanced h = O(log n); degenerate h = O(n) → recursion can overflow

Pre/post-order = Polish notation

(3+4)*5 → pre-order * + 3 4 5 (Polish) · post-order 3 4 + 5 * (RPN, runs on a stack).

Takeaway

Pick the order by when you need the node vs its children. In-order of a BST = sorted. Next: the binary search tree.