Best-First Search Visualizer: Step-by-Step Animation & Complexity

Best-First Search

Category: Tree / Graph | Time: O(n log n) | Space: O(n)

Input Data

Visualization

Visual representation of the data structure

About Best-First Search

A graph search algorithm which explores a graph by expanding the most promising node chosen according to a specified rule. It uses a priority queue to select the next node to visit based on a heuristic cost.

Code Editor

The code is for reference. Editing it won't affect the visualization.

function bestFirstSearch(startNode, target) {
    let pq = new PriorityQueue();
    pq.add(startNode);
    let visited = new Set();

    while (!pq.isEmpty()) {
        let currentNode = pq.poll(); // Get node with best score

        if (currentNode === target) return "Found!";
        
        visited.add(currentNode);

        for (let neighbor of currentNode.neighbors) {
            if (!visited.has(neighbor)) {
                pq.add(neighbor);
            }
        }
    }
    return "Not Found";
}

Variable State

{
  "status": "Starting Search",
  "target": 2
}

Best-First Search: How It Works

Last updated October 28, 2026

Overview

Best-first search is a family of graph searches that always expands the most promising node next, according to a heuristic score. It keeps the frontier in a priority queue rather than a plain queue (BFS) or stack (DFS). Greedy best-first search and A* are the best-known members.

In this visualizer the heuristic is simply the node's value: the smallest value in the priority queue is expanded first. That keeps the example easy to follow; in a real application the score would be something like the straight-line distance to the goal.

The default tree is not a BST (5 has children 18 and 2), and the target is 2. Starting at 10, the search queues 5 and 15, expands 5 because it has the lower score, queues 18 and 2, and then expands 2 — the target — after visiting only three nodes. The path is 10 -> 5 -> 2.

Step by step

Put the start node in a priority queue.
While the queue is not empty, remove the node with the best (lowest) score.
If it is the target, stop.
Mark it visited and add its unvisited neighbours (children) to the priority queue.
If the queue empties, the target is unreachable.

Complexity

Case	Cost	Why
Time (worst)	O(b^d)	b is the branching factor and d the depth; a poor heuristic can explore everything.
Time (good heuristic)	Close to O(d)	A heuristic that points toward the goal expands only nodes on the path.
Space	O(b^d)	The priority queue can hold the whole frontier.

When to use it

Path-finding in games and maps, where a distance estimate to the goal is available.
Puzzle solving (8-puzzle, route planning) where exploring every state is too slow.
As a stepping stone to A*, which adds the cost so far to the heuristic and becomes optimal.

Common mistakes

Greedy best-first search is not guaranteed to find the shortest path; it can be lured down a path that looks good locally.
Without a visited set, graphs with cycles can make it loop forever.
Re-sorting an array on every step, as this demo does for clarity, is O(n log n) per step; real code uses a binary heap.

Worked Example: Best-First Search Dry Run

Generated from the same trace that drives the visualizer above, using the default input.

A dry run is the best way to check your understanding of Best-First Search: follow each row, predict the next one, and compare. The run below takes 29 steps in total. The Line column refers to the line numbers in the code listing above.

Input: Binary tree (see the input box above)
Target: 2
Result: status = Target found!, final_path = 10 -> 5 -> 2

Step	Line	What happens
1	1	status = Starting Search, target = 2
2	3	action = Add start node (10) to priority queue, priority_queue = 10
3	5	condition = 1 > 0, priority_queue = 10
4	6	action = Sort priority queue, priority_queue = 10
5	8	action = Expand best node: 10, current_path = 10, priority_queue =
6	9	current_node = 10, target = 2, condition = 10 === 2
7	11	action = Mark 10 as visited, visited = 10
8	13	action = Checking child 5 of 10
9	14	child = 5, status = Not visited. Adding to queue.
10	15	action = Add 5 to queue, priority_queue = 5
11	13	action = Checking child 15 of 10
12	14	child = 15, status = Not visited. Adding to queue.
13	15	action = Add 15 to queue, priority_queue = 5, 15
14	5	condition = 2 > 0, priority_queue = 5, 15
15	6	action = Sort priority queue, priority_queue = 5, 15
16	8	action = Expand best node: 5, current_path = 10 -> 5, priority_queue = 15
17	9	current_node = 5, target = 2, condition = 5 === 2
18	11	action = Mark 5 as visited, visited = 10, 5
19	13	action = Checking child 18 of 5
20	14	child = 18, status = Not visited. Adding to queue.
21	15	action = Add 18 to queue, priority_queue = 15, 18
22	13	action = Checking child 2 of 5
23	14	child = 2, status = Not visited. Adding to queue.
24	15	action = Add 2 to queue, priority_queue = 15, 18, 2
25	5	condition = 3 > 0, priority_queue = 15, 18, 2
26	6	action = Sort priority queue, priority_queue = 2, 15, 18
27	8	action = Expand best node: 2, current_path = 10 -> 5 -> 2, priority_queue = 15, 18
28	9	current_node = 2, target = 2, condition = 2 === 2
29	10	status = Target found!, final_path = 10 -> 5 -> 2

Frequently Asked Questions

About Best-First Search

What is Best-First Search?

Best-First Search is a graph traversal algorithm that explores a graph by expanding the most promising node chosen according to a specified evaluation function or heuristic. It is considered a 'greedy' algorithm because it always chooses the path that appears best at the moment.

How does Best-First Search work?

It uses a priority queue to store the frontier (or open list) of nodes to visit. The priority of each node is determined by a heuristic function. The algorithm repeatedly extracts the highest-priority node from the queue, checks if it's the goal, and if not, expands its neighbors, adding them to the priority queue.

What is a 'heuristic' in this context?

A heuristic is a function that estimates the 'cost' or 'promise' of a node. It's an educated guess to guide the search towards the goal. For example, in a map, the heuristic might be the straight-line distance to the destination.

Is Best-First Search optimal?

No, a simple greedy Best-First Search is not optimal. It can be deceived by a low-cost path that leads to a dead end, ignoring a slightly higher-cost path that could be a better overall solution. It does not guarantee the shortest path.

How is it different from Dijkstra's and A* Search?

Dijkstra's algorithm always expands the node with the lowest actual path cost from the start, making it optimal. A* Search is a type of Best-First Search that combines Dijkstra's (actual cost) with a heuristic (estimated cost to goal), making it both optimal and efficient. Greedy Best-First Search only uses the heuristic.

What is the time complexity of Best-First Search?

The time complexity is typically O(E + V log V) where V is vertices and E is edges, when implemented with a priority queue. In the worst case, it can explore all nodes.

What is the space complexity?

The space complexity is O(V) to store the nodes in the priority queue and the visited set.

What data structures are needed?

The core data structures are a priority queue to manage the open list of nodes to visit and a hash set or boolean array to keep track of the closed (visited) list to avoid cycles.

Where can I learn more?

You can find a more detailed explanation on GeeksforGeeks.