Search tree
= Search tree
A <rooted tree> whose nodes are partial search states and whose children are possible next choices. Leaves represent completed candidates or terminated branches. <Backtracking> traverses this tree while storing the current path, and <search pruning> removes branches that cannot yield a useful completion.