Learn · DSA · Pattern 7
Trees & BFS/DFS
A linked list had one “next”. A tree lets each node have several children — so it branches. That branching shape is everywhere: files, HTML, org charts, decisions.
Before we start
- What a tree is: nodes with children, not just “next”
- The vocabulary: root, parent, child, leaf
- DFS (go deep) vs BFS (level by level)
- What a Binary Search Tree buys you
- Traverse a tree depth-first and breadth-first
- Solve depth / invert / level-order problems
- Explain why trees give O(log n) search when balanced
Why you’re learning it: trees are one of the most-asked interview topics, and the DFS/BFS traversals here are the same two moves you’ll use on graphs. Do Recursion first. ⏱️ ~35 min.
The vocabulary
Think of a family tree or an org chart. The top node is the root. Each node’s branches lead to its children; the node above is the parent. A node with no children is a leaf. A binary tree just means each node has at most two children (left and right).
The two ways to walk a tree
Go as deep as possible down one branch before backing up. Uses recursion (or a stack). On the tree above: 1 → 2 → 4 → 5 → 3 → 6 → 7.
Visit level by level, top to bottom. Uses a queue. On the tree above: 1 → 2 → 3 → 4 → 5 → 6 → 7.
Rule of thumb: BFS for “shortest path / nearest / level-by-level”; DFS for “explore everything / does a path exist”.
The Binary Search Tree (BST)
A special tree where every left child is smaller and every right child is bigger. That ordering means you search it like binary search — go left or right, halving each step: O(log n) when balanced. It’s the idea under database indexes.
Where you’ll use it — real life
Folders-in-folders and the DOM of a web page are literally trees.
Any “parent/child” hierarchy — departments, product categories, comment threads.
B-trees (a tree variant) let databases find rows in log time.
Decision trees in ML, and shortest-path/routing built on BFS.
Why we practice this
Trees feel intimidating until you realise almost every solution is “do something to this node, then recurse on its children.” Reps make that reflex automatic.
Now YOU do the reps
Out loud: “What’s the difference between DFS and BFS, and when would I use each?” Then log it in your Journal.
Next: Heaps & Greedy →