Deterministic Decision Trees:

A decision tree of N bits is a rooted binary tree. Each internal node of the tree contains an index i $\in$ {1,..., N} and has two children. Each leaf contains either a 1 or a 0. To determine the value of the deterministic decision tree on an input x $\in$ {0, 1}^N we traverse the tree starting at the root. At each internal node we examine the x_i, where i is the index stored at that node. If x_i = 1 we follow the path through the left subtree; if x_i = 0 we follow the path through the right subtree. The value stored at the leaf that we eventually reach is the output of the algorithm. Any decision tree computes an N-bit Boolean function. There are many different deterministic decision trees that compute any given function.

The decision tree complexity of a Boolean function is the minimum depth of any decision tree that computes that function. We denote the decision tree complexity of a Boolean function f by D(f ). The decision tree complexity of a function f is just its classical oracle query complexity. Any decision tree of depth D(f ) determines a minimal sequence of oracle queries that allow us to compute f (x) for any input x.