Course contentsShow
← Machine Learning and Deep Learning
Lesson 1892 of 3,53840. Advanced Prompting TechniquesFree lesson

Search Strategies: BFS and DFS

Breadth-first and depth-first search approaches for exploring the tree of possible reasoning paths.

Search Strategies: BFS and DFS

You'll learn how to systematically explore the tree of reasoning paths in Tree of Thoughts using breadth-first and depth-first search.

The Core Problem

In Tree of Thoughts, you decompose problems into intermediate "thought" states that form a branching tree structure. But which paths should you explore first? Two classic search strategies help you navigate this space efficiently.

Breadth-First Search (BFS)

BFS explores all thoughts at the current level before moving deeper. Think of it like examining every option on the menu's first page before turning to page two.

How it works: Generate and evaluate all possible next thoughts from the current state, keep the top k candidates, then expand each of those in parallel.

Advantages:

  • Finds optimal solutions at shallower depths first
  • Explores diverse paths simultaneously
  • Less likely to get stuck in dead ends

Disadvantages:

  • Memory intensive (stores many states)
  • More API calls per level
  • Higher cost for deep problems

Depth-First Search (DFS)

DFS follows one reasoning path all the way to a conclusion before backtracking. Like reading one book cover-to-cover before starting another.

How it works: Generate one thought, evaluate it, then immediately expand the best one deeper until reaching a terminal state or dead end.

Advantages:

  • Memory efficient (stores only current path)
  • Fewer simultaneous states
  • Faster to find any solution

Disadvantages:

  • May miss better solutions on other branches
  • Can waste time on poor paths
  • Needs backtracking mechanisms

Choosing Your Strategy

Use BFS for problems where solution quality varies significantly and you need the best answer. Use DFS when resources are limited or any valid solution suffices.

Key Takeaway: BFS explores broadly for optimal solutions at higher cost, while DFS dives deep efficiently but risks missing better alternatives—choose based on your problem's solution landscape and resource constraints.