Tree Search Overview

Tree Search Overview

Tree Search is used to find a path from a start state to a goal state.

Each node represents a state:

        A
      / | \
     B  C  D
    /|\ | /\
   E F G H I J

The objective is to reach node J.

---

1. Breadth-First Search (BFS)

Idea

Explore nodes level by level.

Level 0:
A

Level 1:
B C D

Level 2:
E F G H I J

Expansion order:

A → B → C → D → E → F → G → H → I → J

Uses a Queue (FIFO).

Advantages

• Finds shortest path in unweighted graphs.
• Complete.

Disadvantages

• High memory consumption.

---

2. Depth-First Search (DFS)

Idea

Go as deep as possible before backtracking.

Expansion order:

A → B → E → F → G → C → H → D → I → J

Uses a Stack (LIFO).

Advantages

• Low memory usage.
• Simple implementation.

Disadvantages

• May miss the shortest path.
• Can get trapped in deep branches.

---

3. Best-First Search

Idea

Expand the node with the smallest heuristic value.

h(n)

where:

h(n) = estimated distance to goal

Example:

Node	h(n)
B	1
D	3
C	6

Choose:

B first

because:

1 < 3 < 6

Uses a Priority Queue.

Limitation

May find a suboptimal solution because it ignores path cost.

---

4. A* Search

Evaluation Function

f(n)=g(n)+h(n)

where:

g(n)

= actual cost from start

h(n)

= estimated cost to goal

Example:

g(D)=4
h(D)=3

f(D)=7

A* expands the node with the lowest f-value.

Expansion order from the article:

A → B → D → J

Why A* Works Well

A* balances:

• Past cost (g)
• Future estimate (h)

When the heuristic is admissible (never overestimates), A* guarantees the optimal path.

---

Quick Summary

Algorithm	Data Structure	Uses Heuristic	Optimal
BFS	Queue	No	Yes (unweighted)
DFS	Stack	No	No
Best-First	Priority Queue	h(n)	Not always
A*	Priority Queue	g(n)+h(n)	Yes (admissible h)

Memorization Tip

• BFS → Explore by levels
• DFS → Explore by depth
• Best-First → Follow the most promising node
• A* → Follow the cheapest estimated total path