A backtracking algorithm generates, explicitly or implicitly, a state-space tree.

Introduction to the design & analysis of algorithms / Anany Levitin

I wonder that whether the saying always holds. If yes, is it always binary tree? For any problem which can be solved by backtracking, skeleton of the solution can be generalized?


Think about the chess problem or more simple 8-Queen problem are Tic Tac Toe game. The states are not binary trees. As seen from Quoara ;

A state space tree is a tree constructed from all of the possible states of the problem as nodes, connected via state transitions from some initial state as root to some terminal state as a leaf.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.