Is a search node the same as a state?

No. A node is a search record that represents a state and may include path-specific information.

Can a search tree contain a cycle?

The tree structure itself has no cycle, but repeated states along a branch can represent a cycle in the underlying graph.

Does every child increase path cost?

Not necessarily. It increases depth by one action, but the action's cost depends on the problem and can be zero in some models.

AI Glossary / Graphs and symbolic AI / Beginner

Search tree

Definition

A search tree is a tree-shaped representation of the alternatives explored from an initial search node. Each branch extends a possible path, and each node records a state reached by that path together with information needed to continue or reconstruct the search.

What it means

The root represents the starting point. Expanding a node generates children corresponding to possible next actions. A path from the root to a goal node can describe a solution.

A search tree is not necessarily the same as the underlying state-space graph. The graph describes states and possible transitions; the tree describes paths explored from a start. If two paths reach the same state, the tree can contain two separate nodes representing that state.

This distinction matters for both memory and correctness. Treating every path as new can repeat large amounts of work, while merging nodes carelessly can discard a better route or omit history that actually affects future actions. The representation must match the problem.

How it works

Create a root node containing the initial state. Depending on the algorithm, a node may record its parent, the action leading to it, its depth and its accumulated path cost. Parent links make it possible to reconstruct a route after a goal is found.

Select an unprocessed node according to the search strategy. Generate successors and add child nodes for the extensions being considered. The frontier contains nodes awaiting further consideration in many systematic algorithms; it is a changing part of the search, not the entire state space.

The tree is often implicit. A program creates nodes as needed rather than drawing or storing every possible branch in advance. Some methods discard explored branches or regenerate them later to save memory.

Repeated-state detection compares the states represented by nodes. A graph-search procedure can avoid redundant work, but it must handle different path costs and relevant history according to the algorithm's requirements. A finite state graph can unfold into an infinite tree when actions permit cycles.

Three practical examples

A route planner stores parent links in search nodes so that it can reconstruct the recommended sequence of locations.
A puzzle solver notices that two move sequences lead to the same arrangement and applies its repeated-state policy.
A configuration assistant displays a small search-tree excerpt to explain which partial assignments were extended and which were rejected.

Think of it this way

Think of a family of possible travel itineraries written as branching choices. “Go directly to C” and “visit B, then go to C” are different itinerary branches even though both end at C.

A search tree can repeat the same world state, and possible itineraries can grow much faster than the number of locations.

Worked example

Consider four states, S, A, B and G. The available transitions are S to A, S to B, A to G and B to G. All transitions cost one unit.

The state graph has four vertices. Its search tree from S has a root S, children A and B, and one G child below each of those children: five search nodes altogether. The two G nodes represent the same state but have different parents and action histories.

Now add a transition from A back to S. Unrestricted tree expansion can produce S, A, S, A and so on, creating indefinitely many search nodes even though the state graph still has only four vertices.

A suitable cycle or repeated-state check can prevent that repetition. However, the check is justified only when the stored state captures everything relevant to future possibilities. If returning to S changes a resource that matters, that resource must be represented in the state before the two visits can safely be treated as equivalent.

Illustrative case study

In a fictional project, Birch Routes estimates search size by counting distinct locations in a network. Its prototype instead creates a new node for every route prefix, including repeated visits around a loop, and memory use grows unexpectedly.

The team separates state identifiers from search-node records and defines a duplicate-handling policy appropriate to its cost-based algorithm. It also checks that the state includes the constraints affecting future travel.

The case illustrates why a small state graph need not imply a small naive search tree. It does not claim a particular speedup or memory reduction.

Common misconceptions and mistakes

A search tree has one node per unique state. Different paths can create repeated state representations.
Every search tree is stored in full. Many are generated only as exploration proceeds.
A finite state space guarantees a finite unpruned search tree. Cycles can create infinitely many paths.
The frontier is the whole tree. It holds the candidates awaiting processing under the algorithm.
Merging identical-looking locations is always safe. Relevant resources or history may make them different states.
A tree drawing proves all alternatives were explored. It may show only a partial search.

Business use

Search-tree concepts help teams explain why a planning system consumes resources and how it arrived at an answer. A concise trace can identify repeated work, misleading state definitions or unexpected branching.

When estimating scalability, examine branching and search depth alongside the number of distinct states. Also measure how the implementation detects duplicates and reconstructs solutions.

For user-facing explanations, show enough of the path and rejected alternatives to support the decision without implying exhaustive coverage. A visualization of a few explored branches should be labeled as an excerpt rather than evidence of global optimality.

Check your understanding

Why does the four-state worked graph produce five search nodes before the back edge is added?

Answer: G is reached through two distinct paths, so the search tree contains two nodes representing G, one below A and one below B.

Related terms

State space graph
Root
Frontier
Branching factor
Graph search
search node
path cost
repeated-state detection

Learn next

Draw a state graph with two different routes to one state and a loop back to the start. Unfold its first three search-tree levels. Mark repeated states and explain what information would be needed to decide whether those occurrences can be merged.

Sources

Russell and Norvig's search slides, distinguishing states from nodes and discussing repeated states: https://aima.cs.berkeley.edu/slides-pdf/chapter03.pdf

Relevant node and graph-search descriptions were reviewed. The four-state construction and Birch Routes case are original illustrations.

Previous: Search suggest drop-down list Next: Seasonal adjustment