In computational complexity theory, the decision tree model is the model of computation in which an algorithm can be considered to be a decision tree, i.e. a sequence of queries or tests that are done adaptively, so the outcome of previous tests can influence the tests performed next.

Typically, these tests have a small number of outcomes (such as a yes–no question) and can be performed quickly (say, with unit computational cost), so the worst-case time complexity of an algorithm in the decision tree model corresponds to the depth of the corresponding tree. This notion of computational complexity of a problem or an algorithm in the decision tree model is called its decision tree complexity or query complexity.

Decision tree models are instrumental in establishing lower bounds for the complexity of certain classes of computational problems and algorithms. Several variants of decision tree models have been introduced, depending on the computational model and type of query algorithms are allowed to perform.

For example, a decision tree argument is used to show that a comparison sort of ${\displaystyle n}$ items must make ${\displaystyle n\log(n)}$ comparisons. For comparison sorts, a query is a comparison of two items ${\displaystyle a,b}$, with two outcomes (assuming no items are equal): either ${\displaystyle a<b}$ or ${\displaystyle a>b}$. Comparison sorts can be expressed as decision trees in this model, since such sorting algorithms only perform these types of queries.

Decision trees are often employed to understand algorithms for sorting and other similar problems; this was first done by Ford and Johnson.

For example, many sorting algorithms are comparison sorts, which means that they only gain information about an input sequence ${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$ via local comparisons: testing whether ${\displaystyle x_{i}<x_{j}}$, ${\displaystyle x_{i}=x_{j}}$, or ${\displaystyle x_{i}>x_{j}}$. Assuming that the items to be sorted are all distinct and comparable, this can be rephrased as a yes-or-no question: is ${\displaystyle x_{i}>x_{j}}$?

These algorithms can be modeled as binary decision trees, where the queries are comparisons: an internal node corresponds to a query, and the node's children correspond to the next query when the answer to the question is yes or no. For leaf nodes, the output corresponds to a permutation ${\displaystyle \pi }$ that describes how the input sequence was scrambled from the fully ordered list of items. (The inverse of this permutation, ${\displaystyle \pi ^{-1}}$, re-orders the input sequence.)

One can show that comparison sorts must use ${\displaystyle \Omega (n\log(n))}$ comparisons through a simple argument: for an algorithm to be correct, it must be able to output every possible permutation of ${\displaystyle n}$ elements; otherwise, the algorithm would fail for that particular permutation as input. So, its corresponding decision tree must have at least as many leaves as permutations: ${\displaystyle n!}$ leaves. Any binary tree with at least ${\displaystyle n!}$ leaves has depth at least ${\displaystyle \log _{2}(n!)=\Omega (n\log _{2}(n))}$, so this is a lower bound on the run time of a comparison sorting algorithm. In this case, the existence of numerous comparison-sorting algorithms having this time complexity, such as mergesort and heapsort, demonstrates that the bound is tight.