Binary tree & traversals
Scenario
Your file manager organizes folders inside folders. To find a file or list all folders, you must systematically visit every directory without missing any or looping forever.
How do you systematically visit every node in a branching hierarchy exactly once?
Why it exists
Problem: Linear data structures like arrays have a single sequential order. Hierarchical data has multiple branches, making simple sequential loops insufficient to visit every element.
Naive approach: Arbitrary pointer jumping without a structured traversal order, risking missing nodes or getting stuck in cycles.
Better idea: Define structured traversal orders (pre-order, in-order, post-order, level-order) that visit every node exactly once by systematically exploring left and right subtrees.
Mental model
A node plus a left subtree plus a right subtree, all the way down.
At each node, you decide the relative sequence in which to process the current node's value versus recursing into its left and right subtrees. Depth (distance from root down) and height (distance from leaf up) define node positions, while traversals create a total ordering over all N nodes.
Repeated decision: at this node, which do I do -- visit it, go left, or go right?
Explanation
A binary tree is a non-linear data structure where each node has at most two children, conventionally termed `left` and `right`.
Core Terms:
- `root`: The topmost node of the tree with no parent.
- `leaf`: A node with no children (`left is None` and `right is None`).
- `depth`: Number of edges from the `root` down to a specific node (root has depth 0).
- `height`: Number of edges on the longest downward path from a node to a leaf (leaf has height 0).
- `complete`: Every level is fully filled except possibly the last, which is filled left-to-right.
- `full`: Every node has either 0 or 2 children.
- `balanced`: The left and right subtrees of every node differ in height by at most 1.
Traversing a binary tree means visiting every node in a specific sequence. Because trees branch, there are four standard orders:
1. Pre-order (DFS): Visit Node -> Recurse Left -> Recurse Right
2. In-order (DFS): Recurse Left -> Visit Node -> Recurse Right
3. Post-order (DFS): Recurse Left -> Recurse Right -> Visit Node
4. Level-order (BFS): Visit nodes level by level, top to bottom, left to right.
Walkthrough on a 5-node tree:
Given root `1` with left child `2` and right child `3`. Node `2` has children `4` and `5`.
Structure:
1
/ \
2 3
/ \
4 5
1. Pre-order sequence: Visit `1`, descend left to `2`, visit `2`, descend left to `4`, visit `4` (leaf, return to `2`), descend right to `5`, visit `5` (leaf, return to `1`), descend right to `3`, visit `3`. Output: `[1, 2, 4, 5, 3]`.
2. In-order sequence: Descend left to `4`, visit `4`, return to `2`, visit `2`, descend right to `5`, visit `5`, return to `1`, visit `1`, descend right to `3`, visit `3`. Output: `[4, 2, 5, 1, 3]`.
3. Post-order sequence: Descend to leaves first: visit `4`, visit `5`, return to `2` and visit `2`, return to `1`, descend right to visit `3`, return to `1` and visit `1`. Output: `[4, 5, 2, 3, 1]`.
4. Level-order sequence: Level 0 (`[1]`), Level 1 (`[2, 3]`), Level 2 (`[4, 5]`). Output: `[1, 2, 3, 4, 5]`.
Tree Reconstruction from Traversals:
Given pre-order and in-order traversal arrays, the first element of the pre-order array is always the root. Finding that root value inside the in-order array splits the in-order array into left subtree elements (all values before the root index) and right subtree elements (all values after the root index), allowing recursive top-down tree construction.
Key points
- Total Order Invariant: Every valid traversal produces a deterministic sequence of length N where every node is visited exactly once.
- Depth vs Height: Depth measures distance from the root downwards; height measures distance to the furthest leaf upwards.
- Complexity: All four traversals run in O(n) time to visit n nodes, using O(h) call-stack space for DFS (where h is height) or O(w) queue space for BFS (where w is max width).
Pattern: Tree Traversal
Recognition cues:
- hierarchical node structure
- need to visit all nodes in a structural order
- parent-child parent relationships
Failure signals
- You need to list or process every element in a hierarchical file system or XML/HTML DOM tree.
Engineering examples
HTML DOM tree traversal
Render or apply styles across all nested elements in a web page DOM.
DOM elements form a tree where parents contain child nodes. Traversing pre-order or post-order allows hierarchical rendering and event bubbling.
Compiler Abstract Syntax Trees (AST)
Evaluate expression trees like (2 + 3) * 4.
Evaluating operands before their parent operator requires a post-order traversal over the expression tree.
When not to use
- Sequential indexed lookups: Arrays offer O(1) random access by index, whereas binary trees require O(h) traversal to reach a target node.
Common mistakes
- Assuming a generic binary tree is sorted: A general binary tree places elements arbitrarily. Only a Binary Search Tree (BST) maintains sorted order invariants.
- Confusing traversal order with insertion order: The order nodes are visited depends on the traversal type (pre/in/post/level), not on when the nodes were created or inserted.
- Confusing node depth with node height: Depth increases as you go down from the root; height increases as you go up from the leaves.
Recall questions
- What is the difference between node depth and node height?
- Which order does pre-order traversal visit nodes in?
- Why is the time complexity of traversing an N-node binary tree O(N)?
Questions & answers
Given a binary tree, return its pre-order traversal as a list of integers.
Use a recursive helper or an explicit stack. Visit the node, append its value, then recurse left and right.
Approach: Pre-order traversal (Root -> Left -> Right).
Construct a binary tree given its pre-order and in-order traversal arrays.
The first element of pre-order is the root. Find that root in the in-order array to split into left and right subtrees, then recurse.
Approach: Use pre-order to pick roots and in-order to determine left/right subtree node counts.
Interesting facts
- Any binary tree can be uniquely reconstructed if you are given its in-order traversal along with either its pre-order or post-order traversal.
Continue learning
Previous: Recursive tree thinking
Next: DFS: pre / in / post
Next: Level-order (BFS)
Related: Recursive tree thinking
Related: DFS: pre / in / post
Related: Level-order (BFS)