Understanding the state space tree

The processing of a backtracking solution generates a state space tree. Every backtracking solution starts from a problem state and tries to reach one or more solution states by making choices. If the choices do not lead to a solution state, we backtrack and make different choices.

A space state tree is a tree that represents all the possible states (solution or nonsolution), starting from the root as the initial state (problem state) to the leaf as a terminal state (potential solution state). The intermediate states can either be fulfilling or defying states. A fulfilling state leads to a possible solution, while a defying state can never lead to a solution. We decide if a state is fulfilling or defying using some algorithm/function specific to the problem. Not all backtracking problems have to defy states in their state space tree.