Skip to content
Tutorials Center
My learning

Topics

Lesson 6 of 46 ยท Uninformed Search

Tree Search and Graph Search

Build the generic AI search algorithm in Python: frontier, node expansion, explored set and goal test. See why repeated states matter and how to count nodes expanded.

You now know how to describe a problem with states, actions and a goal test. This lesson builds the engine that solves it. Every search algorithm in this course, from breadth-first search to A*, is a variation on a single skeleton: keep a collection of unexplored possibilities, pick one, check whether it is a goal, and if not, replace it by its successors.

The variations differ in exactly one decision, which possibility to pick next. We will write the skeleton once, in a way that works with any Problem, and discover why a naive version can run forever or waste enormous effort when the same state can be reached in several ways.

Search trees and nodes

Imagine unfolding the state-space graph from the initial state: the start is the root, its successors are children, their successors are grandchildren, and so on. That unfolded structure is the search tree. The same state can appear many times in it, once for each different path that reaches it.

A tree is made of nodes. A node is more than a state: it also records where it came from.

  • state: the state it represents
  • parent: the node that generated it
  • action: the action applied to the parent
  • path_cost: the cost from the root to here
  • depth: the number of steps from the root

The parent links let us rebuild the solution at the end by walking back to the root.

Two collections organize the work:

  • The frontier (also called the open list) holds nodes that have been generated but not yet expanded.
  • Expanding a node means asking the problem for its actions, computing each resulting state and creating one child node per action.
graph TD
    R["root: start state"] --> A["child A"]
    R --> B["child B"]
    A --> C["grandchild"]
    A --> D["grandchild"]
    B --> E["grandchild"]
    classDef done fill:#dbeafe,stroke:#2563eb,color:#1e3a8a
    classDef edge fill:#fef3c7,stroke:#d97706,color:#78350f
    class R,A done
    class B,C,D,E edge

Expanded nodes (blue) have had their children generated. The frontier (orange) is everything at the edge, waiting its turn.

The generic skeleton

The algorithm is only a few lines:

  1. Put a node for the initial state on the frontier.
  2. If the frontier is empty, fail.
  3. Remove a node from the frontier. If its state passes the goal test, return its path.
  4. Otherwise expand it and add the children to the frontier. Go to step 2.

Choosing the removal rule gives the strategy. A queue (first in, first out) produces breadth-first search; a stack (last in, first out) gives depth-first search; a priority queue gives uniform-cost search and A*. The next lessons try each one.

Python The generic search skeleton

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice what tree_search never does: it never remembers that it has already seen a state. In this graph, S is a neighbor of A, so the search happily generates S again as a child of A, then expands it again, and so on.

Repeated states and the explored set

A state that can be reached by more than one path creates redundant paths. Worse, a loop (a path that returns to a state it already visited) makes the search tree infinite even when the state space is tiny. Depth-first search can then run forever without ever finding a goal that is right next door.

Python A loop that traps tree search

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Depth-first tree search keeps bouncing between S and A until the safety limit stops it. The fix is the explored set (or closed list): remember every state that has been generated, and never create a node for a state you have already seen. This turns tree search into graph search. In code the change is two lines, the reached set above.

graph LR
    S["S"] --> A["A"]
    A --> S
    A --> B["B"]
    B --> G["G (goal)"]

A loop between S and A: a tree-search stack keeps expanding S then A forever, while graph search remembers S.

Watch out: an explored set trades memory for time. It must store every state ever generated, so on huge state spaces it can run out of memory. Also, when step costs differ, a plain "never look at a state twice" rule can throw away a cheaper path to the same state; algorithms that care about cost (uniform-cost, A*) must be able to replace a worse path with a better one.

How do you compare algorithms? Four standard measures:

  • Completeness: does it always find a solution when one exists?
  • Optimality: is the solution it finds the cheapest?
  • Time complexity: usually counted as the number of nodes generated or expanded.
  • Space complexity: the maximum number of nodes held in memory.

For trees, complexity is written with the branching factor b (successors per node), the depth d of the shallowest goal and m, the maximum depth. A search that explores everything down to depth d touches about b^d nodes, which is why the branching factor of 2.67 from the 8-puzzle matters so much.

The next experiment shows how much the explored set saves. On an n by n grid, the number of distinct states is just nยฒ, but the number of paths is exponential. We count nodes expanded by breadth-first search with and without it.

Python Nodes expanded: tree search versus graph search

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The graph-search count stays near the number of states, while tree search grows by a factor of roughly ten with every extra row and column. A 10 by 10 grid would be hopeless for tree search. Whenever a problem has repeated states, which means almost every real problem, use graph search.

If graph algorithms feel rusty, review graph representations, breadth-first search and depth-first search in the DSA tutorial. The AI versions differ mainly in that the graph is not stored: it is generated on demand from actions and result, which is how a program can search a puzzle with a trillion states without ever listing them.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does the frontier contain?

    The frontier is the boundary between explored and unexplored parts of the search tree. Each step removes one node from it and adds its children.
  2. 2. What turns tree search into graph search?

    Remembering visited states removes redundant paths and prevents loops, which is the defining difference.
  3. 3. Why can depth-first tree search fail to terminate on a finite state space?

    If a path can return to an earlier state, the unfolded tree has infinite branches, and depth-first search can follow one forever.
  4. 4. Why does each Node keep a reference to its parent?

    Following parent links from the goal node back to the root, then reversing, gives the sequence of states and actions.
  5. 5. What is the main cost of using an explored set?

    The set grows with the number of distinct states visited. That is why memory-bounded algorithms exist.

Summary

  • A search tree is the state-space graph unfolded from the start; nodes carry state, parent, action, path cost and depth.
  • All uninformed and informed search algorithms share one skeleton: pick a node from the frontier, goal-test it, expand it.
  • The strategy is the rule for choosing from the frontier: queue, stack or priority queue.
  • Tree search can loop forever and repeats work; graph search avoids both by remembering explored states.
  • Algorithms are compared by completeness, optimality, time and space, usually in terms of branching factor and depth.

Next: Breadth-First and Depth-First Search for AI.