Coding Pattern:
Tree Breadth First Search
This pattern has an earnable cheat sheet.
Note
Familiarize yourself with the tree and deque data structures before proceeding past this section.
Pattern concept
Step 1 of 33
Use ← → arrow keys
Code snippets
How to identify
Does the problem involve any of these?
- Process the nodes by layers
- Binary Tree Level Order Traversal from Right to Left: Find the level with the most nodes.
- Max Width of Binary Tree: Find the level with the most nodes.
- Binary Tree Zigzag Traversal: Visit nodes level by level in alternating order.
- Symmetric Tree: Compare left and right nodes on the same layer to test for symmetry.
- Operating on nodes based on their level in the tree
- Cousins in a Binary Tree: Determine if nodes are on the same level but not siblings.
Note
BFS usually takes O(n) to traverse the tree, and O(w) space where w is the widest level of the tree.