Recursive top-down and bottom-up traversals on hierarchical structures
Traverse binary or general trees by recurring deep along branches, computing subtree metrics bottom-up (postorder) or passing state top-down (preorder).
Core Invariant: Recursive Trust: Assume `dfs(node.left)` and `dfs(node.right)` return the correct subtree answers. Combine them at `node` with the base case (`if not node: return base_val`).
Level-by-level processing or shortest path in terms of edge counts (Tree BFS is cleaner).
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def diameter_of_binary_tree(root: TreeNode | None) -> int:
max_diameter = 0
def dfs(node: TreeNode | None) -> int:
nonlocal max_diameter
if not node:
return 0 # Height of empty subtree
# Postorder: solve children first
left_height = dfs(node.left)
right_height = dfs(node.right)
# Invariant: longest path through current node spans both subtrees
max_diameter = max(max_diameter, left_height + right_height)
# Return single branch height upward to parent
return 1 + max(left_height, right_height)
dfs(root)
return max_diameter# | Problem | Difficulty | Top Companies↓ | Frequency | Acceptance | |
|---|---|---|---|---|---|---|
| #200 | Number of Islands ArrayDepth-First SearchBreadth-First SearchUnion-FindMatrix | Medium | 100% | 64.7% | ||
| #207 | Course Schedule Depth-First SearchBreadth-First SearchGraph TheoryTopological SortDirected Acyclic Graph | Medium | 100% | 51.8% | ||
| #79 | Word Search ArrayStringBacktrackingDepth-First SearchMatrix | Medium | 100% | 47.7% | ||
| #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% | ||
| #332 | Reconstruct Itinerary ArrayStringDepth-First SearchGraph TheorySortingHeap (Priority Queue)Eulerian CircuitEulerian PathSemi-Eulerian Graph | Hard | 100% | 44.7% | ||
| #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% | ||
| #103 | Binary Tree Zigzag Level Order Traversal TreeBreadth-First SearchBinary Tree | Medium | 100% | 64.1% | ||
| #64 | Minimum Path Sum ArrayDynamic ProgrammingMatrix | Medium | 100% | 68.5% | ||
| #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% | ||
| #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% | ||
| #211 | Design Add and Search Words Data Structure StringDepth-First SearchDesignTrie | Medium | 88% | 0.5% | ||
| #235 | Lowest Common Ancestor of a Binary Search Tree TreeDepth-First SearchBinary Search TreeBinary TreeBinary LiftingLowest Common Ancestor | Medium | 100% | 70.9% | ||
| #417 | Pacific Atlantic Water Flow ArrayDepth-First SearchBreadth-First SearchMatrix | Medium | 100% | 61.2% | ||
| #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% | ||
| #2385 | Amount of Time for Binary Tree to Be Infected Hash TableTreeDepth-First SearchBreadth-First SearchBinary Tree | Medium | 100% | 0.7% | ||
| #490 | The Maze ArrayDepth-First SearchBreadth-First SearchMatrix | Medium | 63% | 60.5% | ||
| #2603 | Collect Coins in a Tree ArrayTreeGraph TheoryTopological Sort | Hard | 100% | 39.5% | ||
| #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% | ||
| #886 | Possible Bipartition Depth-First SearchBreadth-First SearchUnion-FindGraph TheoryGraph ColoringBipartite Graph | Medium | 77% | 52.8% | ||
| #642 | Design Search Autocomplete System StringDepth-First SearchDesignTrieSortingHeap (Priority Queue)Data Stream | Hard | 75% | 50.0% | ||
| #101 | Symmetric Tree TreeDepth-First SearchBreadth-First SearchBinary Tree | Easy | 68% | 61.6% | ||
| #261 | Graph Valid Tree Depth-First SearchBreadth-First SearchUnion-FindGraph Theory | Medium | 100% | 50.1% | ||
| #947 | Most Stones Removed with Same Row or Column Hash TableDepth-First SearchUnion-FindGraph TheoryBipartite Graph | Medium | 100% | 63.2% | ||
| #743 | Network Delay Time Depth-First SearchBreadth-First SearchGraph TheoryHeap (Priority Queue)Shortest PathDijkstra's Algorithm | Medium | 100% | 61.0% | ||
| #110 | Balanced Binary Tree TreeDepth-First SearchBinary Tree | Easy | 100% | 0.6% | ||
| #572 | Subtree of Another Tree TreeDepth-First SearchString MatchingBinary TreeHash Function | Easy | 89% | 0.5% | ||
| #96 | Unique Binary Search Trees MathDynamic ProgrammingTreeBinary Search TreeBinary Tree | Medium | 88% | 0.6% | ||
| #226 | Invert Binary Tree TreeDepth-First SearchBreadth-First SearchBinary Tree | Easy | 87% | 80.2% |
Browse company-specific interview problem lists and recency breakdowns:
Master core algorithmic patterns tested in FAANG & Big Tech coding interviews.
Recursive top-down and bottom-up traversals on hierarchical structures It is categorized under Trees & Graphs and features 351 curated interview problems across Easy (40), Medium (223), and Hard (88) difficulties.
Companies frequently asking Tree Depth-First Search (DFS) 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.