Level-order traversal and horizontal tier exploration using queues
Traverse tree level by level using a FIFO queue, processing all nodes at depth D before any node at depth D+1.
Core Invariant: Level Snapshot: At the start of each while loop iteration, `len(queue)` EXACTLY equals the number of nodes on the current level. Process that fixed count in a loop before touching the next level.
Path sum from root to leaf or deep ancestor queries (Tree DFS is simpler and uses less auxiliary memory).
from collections import deque
def level_order(root: TreeNode | None) -> list[list[int]]:
if not root:
return []
levels = []
queue = deque([root])
while queue:
level_size = len(queue) # Snapshot number of nodes at this depth
curr_level = []
for _ in range(level_size):
node = queue.popleft()
curr_level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
levels.append(curr_level)
return levels# | Problem | Difficulty | Top Companies↓ | Frequency | Acceptance | |
|---|---|---|---|---|---|---|
| #200 | Number of Islands ArrayDepth-First SearchBreadth-First SearchUnion-FindMatrix | Medium | 100% | 64.7% | ||
| #994 | Rotting Oranges ArrayBreadth-First SearchMatrix | Medium | 100% | 59.0% | ||
| #207 | Course Schedule Depth-First SearchBreadth-First SearchGraph TheoryTopological SortDirected Acyclic Graph | Medium | 100% | 51.8% | ||
| #127 | Word Ladder Hash TableStringBreadth-First SearchBidirectional Search | Hard | 100% | 46.0% | ||
| #210 | Course Schedule II Depth-First SearchBreadth-First SearchGraph TheoryTopological Sort | Medium | 100% | 55.9% | ||
| #124 | Binary Tree Maximum Path Sum Dynamic ProgrammingTreeDepth-First SearchBinary TreeDP on Trees | Hard | 100% | 42.5% | ||
| #297 | Serialize and Deserialize Binary Tree StringTreeDepth-First SearchBreadth-First SearchDesignBinary Tree | Hard | 100% | 61.1% | ||
| #269 | Alien Dictionary ArrayStringDepth-First SearchBreadth-First SearchGraph TheoryTopological SortDirected Acyclic Graph | Hard | 100% | 0.4% | ||
| #98 | Validate Binary Search Tree TreeDepth-First SearchBinary Search TreeBinary Tree | Medium | 88% | 36.0% | ||
| #236 | Lowest Common Ancestor of a Binary Tree TreeDepth-First SearchBinary TreeBinary LiftingLowest Common Ancestor | Medium | 100% | 69.7% | ||
| #543 | Diameter of Binary Tree TreeDepth-First SearchBinary TreeDP on Trees | Easy | 88% | 65.8% | ||
| #787 | Cheapest Flights Within K Stops Dynamic ProgrammingDepth-First SearchBreadth-First SearchGraph TheoryHeap (Priority Queue)Shortest Path | Medium | 100% | 42.2% | ||
| #695 | Max Area of Island ArrayDepth-First SearchBreadth-First SearchUnion-FindMatrix | Medium | 100% | 74.1% | ||
| #104 | Maximum Depth of Binary Tree TreeDepth-First SearchBreadth-First SearchBinary Tree | Easy | 100% | 78.4% | ||
| #133 | Clone Graph Hash TableDepth-First SearchBreadth-First SearchGraph Theory | Medium | 100% | 65.7% | ||
| #329 | Longest Increasing Path in a Matrix ArrayDynamic ProgrammingDepth-First SearchBreadth-First SearchGraph TheoryTopological SortMemoizationMatrixDirected Acyclic Graph | Hard | 93% | 0.6% | ||
| #341 | Flatten Nested List Iterator StackTreeDepth-First SearchDesignQueueIterator | Medium | 100% | 65.8% | ||
| #102 | Binary Tree Level Order Traversal TreeBreadth-First SearchBinary Tree | Medium | 100% | 73.0% | ||
| #863 | All Nodes Distance K in Binary Tree Hash TableTreeDepth-First SearchBreadth-First SearchBinary Tree | Medium | 89% | 67.8% | ||
| #815 | Bus Routes ArrayHash TableBreadth-First Search | Hard | 100% | 47.4% | ||
| #103 | Binary Tree Zigzag Level Order Traversal TreeBreadth-First SearchBinary Tree | Medium | 100% | 64.1% | ||
| #934 | Shortest Bridge ArrayDepth-First SearchBreadth-First SearchMatrix | Medium | 100% | 59.6% | ||
| #827 | Making A Large Island ArrayDepth-First SearchBreadth-First SearchUnion-FindMatrix | Hard | 90% | 56.9% | ||
| #721 | Accounts Merge ArrayHash TableStringDepth-First SearchBreadth-First SearchUnion-FindSorting | Medium | 83% | 61.6% | ||
| #752 | Open the Lock ArrayHash TableStringBreadth-First SearchBidirectional Search | Medium | 100% | 61.4% | ||
| #407 | Trapping Rain Water II ArrayBreadth-First SearchHeap (Priority Queue)Matrix | Hard | 100% | 0.6% | ||
| #968 | Binary Tree Cameras Dynamic ProgrammingTreeDepth-First SearchBinary TreeDP on Trees | Hard | 100% | 0.5% | ||
| #199 | Binary Tree Right Side View TreeDepth-First SearchBreadth-First SearchBinary Tree | Medium | 88% | 70.7% | ||
| #235 | Lowest Common Ancestor of a Binary Search Tree TreeDepth-First SearchBinary Search TreeBinary TreeBinary LiftingLowest Common Ancestor | Medium | 100% | 70.9% | ||
| #126 | Word Ladder II Hash TableStringBacktrackingBreadth-First SearchBidirectional Search | Hard | 100% | 27.8% | ||
| #1293 | Shortest Path in a Grid with Obstacles Elimination ArrayBreadth-First SearchMatrix | Hard | 100% | 46.5% | ||
| #1091 | Shortest Path in Binary Matrix ArrayBreadth-First SearchMatrix | Medium | 81% | 51.8% | ||
| #987 | Hard | 100% | 54.2% | |||
| #417 | Pacific Atlantic Water Flow ArrayDepth-First SearchBreadth-First SearchMatrix | Medium | 100% | 61.2% | ||
| #317 | Shortest Distance from All Buildings ArrayBreadth-First SearchMatrix | Hard | 100% | 45.0% | ||
| #230 | Kth Smallest Element in a BST TreeDepth-First SearchBinary Search TreeBinary Tree | Medium | 88% | 77.0% | ||
| #130 | Surrounded Regions ArrayDepth-First SearchBreadth-First SearchUnion-FindMatrix | Medium | 87% | 0.5% | ||
| #924 | Minimize Malware Spread ArrayHash TableDepth-First SearchBreadth-First SearchUnion-FindGraph Theory | Hard | 100% | 0.4% | ||
| #542 | 01 Matrix ArrayDynamic ProgrammingBreadth-First SearchMatrix | Medium | 100% | 54.4% | ||
| #2385 | Amount of Time for Binary Tree to Be Infected Hash TableTreeDepth-First SearchBreadth-First SearchBinary Tree | Medium | 100% | 0.7% | ||
| #1197 | Minimum Knight Moves Breadth-First SearchHeuristic SearchBidirectional SearchA* Search | Medium | 88% | 42.0% | ||
| #490 | The Maze ArrayDepth-First SearchBreadth-First SearchMatrix | Medium | 63% | 60.5% | ||
| #279 | Perfect Squares MathDynamic ProgrammingBreadth-First SearchKnapsack ProblemComplete Knapsack | Medium | 100% | 56.7% | ||
| #2603 | Collect Coins in a Tree ArrayTreeGraph TheoryTopological Sort | Hard | 100% | 39.5% | ||
| #286 | Walls and Gates ArrayBreadth-First SearchMatrix | Medium | 100% | 64.1% | ||
| #694 | Number of Distinct Islands ArrayHash TableDepth-First SearchBreadth-First SearchUnion-FindSortingMatrixHash Function | Medium | 92% | 0.6% | ||
| #337 | House Robber III Dynamic ProgrammingTreeDepth-First SearchBinary TreeDP on Trees | Medium | 88% | 56.1% | ||
| #733 | Flood Fill ArrayDepth-First SearchBreadth-First SearchMatrix | Easy | 88% | 0.7% | ||
| #100 | Same Tree TreeDepth-First SearchBreadth-First SearchBinary Tree | Easy | 85% | 67.5% | ||
| #105 | Construct Binary Tree from Preorder and Inorder Traversal ArrayHash TableDivide and ConquerTreeBinary Tree | Medium | 83% | 69.1% |
Browse company-specific interview problem lists and recency breakdowns:
Master core algorithmic patterns tested in FAANG & Big Tech coding interviews.
Level-order traversal and horizontal tier exploration using queues It is categorized under Trees & Graphs and features 381 curated interview problems across Easy (40), Medium (235), and Hard (106) difficulties.
Companies frequently asking Tree Breadth-First Search (BFS) questions include Google, Amazon, Meta, Microsoft, Bloomberg, Uber.
Start by studying the algorithmic strategy and template code, then practice Easy and Medium problems before attempting Hard problems under timed conditions.