AI

Tree of Thoughts Planning Agent

Medium
Agents

Tree of Thoughts Planning

ToT explores multiple parallel reasoning paths, unlike linear chain-of-thought.

Task

Implement TreeOfThoughtsAgent with:

  1. expand(): Generate breadth child thoughts from a parent via LLM.
  2. evaluate(): Score each thought (0-1).
  3. bfs(): BFS tree search pruning thoughts below prune_threshold.
  4. best_path(): Return list of thought contents from root to best terminal.

Constraints

  • Prune thoughts with score < prune_threshold.
  • Max depth = depth_limit.
  • BFS explores all depth-D nodes before depth D+1.
  • best_path traces parent_id chain back to root.

Examples

Example 1:
Input: agent.bfs('How to reverse a list?')
Output: Best terminal thought with path: ['Use two pointers', 'Swap from ends inward', 'O(n) time O(1) space']
Explanation: BFS explores breadth=3 paths; highest-scoring terminal returned.

Starter Code

from typing import List, Optional
from dataclasses import dataclass, field
import uuid

@dataclass
class Thought:
    thought_id: str = field(default_factory=lambda: str(uuid.uuid4())[:8])
    content: str = ''
    parent_id: Optional[str] = None
    score: float = 0.0
    depth: int = 0
    is_terminal: bool = False

class TreeOfThoughtsAgent:
    def __init__(self, llm_fn: callable, breadth: int = 3, depth_limit: int = 3, prune_threshold: float = 0.3):
        self.llm_fn = llm_fn
        self.breadth = breadth
        self.depth_limit = depth_limit
        self.prune_threshold = prune_threshold
        self.thoughts: dict = {}

    def expand(self, parent: Thought) -> List[Thought]:
        # Generate breadth child thoughts
        pass

    def evaluate(self, thought: Thought, problem: str) -> float:
        # Score thought 0-1
        pass

    def bfs(self, problem: str) -> Optional[Thought]:
        # BFS tree search, return best terminal thought
        pass

    def best_path(self, terminal: Thought) -> List[str]:
        pass
Lines: 1Characters: 0
Ready
The AI Interview - Master AI/ML Interviews