Breadth-first Search (BFS)
Concept
Two main scenarios of using BFS: do traversal or find the shortest path. Typically, it happens in a tree or a graph.
In tree/graph traversal: It's level-order traversal, the nodes closer to the root node will be traversed earlier
In finding shortest path: If a node X is added to the queue in the kth round, the length of the shortest path between the root node and X is exactly k.
Implementation
1.Queue
2.Queue + set (avoiding cycle)
Template
Find the length of a shortest path from root to target.
Every time, you move down one level down, in this case, you will find the shortest length from root to target.
Template II
Avoid cycle in a graph.
[Medium] No.279 Perfect Squares
Approach: BFS + greedy
Time Complexity: O(N^h/2), where h is the maximal number of recursion that could happen.
Space Complexity: check the link.
[Medium] No.103 Binary Tree Zigzag Level Order Traversal
Approach: BFS
Time Complexity: O(N), where N is the number of nodes in the tree.
Space Complexity: O(N), where N is the number of nodes in the tree.