Depth First Search

⏱ Time: O(N)💾 Space: O(H)

Traverse deep into a graph or tree before backtracking. Often implemented using recursion or an explicit stack. Excellent for exploring all paths or finding specific structures like connected components.

🎯 When to Use

  • ✓Exploring all possible paths
  • ✓Tree traversal (pre/in/post order)
  • ✓Finding connected components
  • ✓Backtracking problems

📝 Pseudocode

Depth First Search TemplateO(N)
1function dfs(node):
2  if node is null:
3    return
4  
5  // pre-order processing
6  dfs(node.left)
7  // in-order processing
8  dfs(node.right)
9  // post-order processing

🏢 Real-World Use Cases

Meta
DOM Tree Traversal

Traversing nested DOM elements to render or update UI components efficiently.

💡 Practice Problems (2)

1.Maximum Depth of Binary TreeEasy
→
2.Invert Binary TreeEasy
→
← Back to Patterns