decision tree

A tree in which each internal node is a question or choice and each path from the root to a leaf is one complete outcome.

In more detail

In sorting, each node is a comparison and each leaf one possible ordering, and the tree's depth is the worst-case number of comparisons. In backtracking, each node is a partial solution and each branch one choice, and pruning cuts off whole subtrees. The same picture explains both a lower bound and a search strategy.

Related terms

Taught in

References