Breadth-First Search
See all coding puzzles and patterns here.
Algorithm Description
A breadth-first search is an algorithm in which a data structure is modeled into a tree and traversed one level at a time, in search of an element. A depth-first traversal, by comparison, searches down toward the leaves first.
Breadth-first search should be used when trying to find the shortest path between two nodes.
Performance Characteristics
Let $n$ equal the number of nodes in the tree.
Since we may need to visit every node in the tree, the runtime complexity of this technique is $O(n)$.
Space complexity can vary, depending on the characteristics of the tree. If the tree is a binary tree, like a binary search tree, then the auxiliary space complexity will be $O(n)$ since the bottom-most layer may contain $\frac{n}{2}$ items.
In general, if there is a branching factor $k$ for every node (i.e., every node has at most $k$ children), then each layer $i$, starting with $0$ as the root, will have $k^i$ nodes and the total will be $n \approx \sum_i k^i$. So the bottom-most layer $b$ will contain $\frac{k^b}{n} \lt n$ items, which implies an auxiliary space complexity of $O(\frac{n}{k})$ or $O(n)$ if we want to be less precise.
In the best case, the tree is a linked list, which would result in a space complexity of $\Omega(1)$.
Puzzles
| Puzzle | Difficulty | External Link |
| All Nodes Distance K in a Binary Tree | Medium | Leetcode 863 |
| Binary Tree Right Side View | Medium | Leetcode 199 |
| Binary Tree Vertical Order Traversal | Medium | Leetcode 314 (Premium) |
| Brace Permutations | Medium | |
| Clone a Graph | Medium | Leetcode 133 |
| House Robber III | Medium | Leetcode 337 |
| Letter Combinations of a Phone Number | Medium | Leetcode 17 |
| Number of Enclaves | Medium | Leetcode 1020 |
