Decision tree size
Minimum number of leaves of a deterministic decision tree computing f.
also written:
DT size, leaf complexity, \mathrm{L}(f)
Definition
The minimum number of leaves in a deterministic decision tree computing $f$. One usually works with $\log \mathrm{DTsize}(f)$, which sits between $\log n$-ish quantities and $\mathrm{D}(f)$: $$\log_2 \mathrm{DTsize}(f) \le \mathrm{D}(f) \le \mathrm{DTsize}(f)-1 .$$ Size, unlike depth, is sensitive to "wide but shallow" structure and is the natural notion for the quantum speedup for decision-tree size line of work.
Basic facts
- $\mathrm{Q}_{2/5}(f) = O(\sqrt{\mathrm{DTsize}(f)})$, even for relations, and even if the tree is randomized.
- Size can be exponentially larger than depth ($\mathrm{DTsize} \le 2^{\mathrm{D}}$).
Relations to other measures
A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{DTsize}(f)\). “\(\mathrm{DTsize}(f)\) in terms of it” is the pair with \(\mathrm{DTsize}(f)\) on the left (the matrix row); the other column is the reverse. Each cell gives, per setting, the exponent range a,b of the best bounds known — \(\mathrm{M_1} = \Omega(\mathrm{M_2}^{a})\) below and \(\mathrm{M_1} = O(\mathrm{M_2}^{b})\) above, so \(a = b\) means settled — or a glyph where no polynomial bound exists at all. These are derived, not just read off the exponent table, so they are present for pairs the table does not cover. A cell with no entry for a setting is one where the zoo has nothing at that setting, and a — one where the ordered pair is empty in all three; derived marks a direction with no hand-written relation record behind it, which is the common case and not a hole.
The 5 above are this entry’s hand-picked neighbours; the other 88 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| OR total | \(n+1\) | The caterpillar has $n+1$ leaves. Conversely the unique $0$-input sits at depth $n$ in any tree, and each of the $n$ branches leaving that path reaches a different leaf. |
| AND total | \(n+1\) | Mirror of OR: the caterpillar has $n+1$ leaves and no tree has fewer. |
| PARITY total | \(2^n\) | Every leaf is a full assignment. |
| MAJORITY total | \(O\!\big(2^n/\sqrt n\big)\) putative | The counting tree -- query until one side reaches $(n+1)/2$ -- has exactly $\binom{n+1}{(n+1)/2}$ leaves, since the stopping sequences of each type number $\sum_{j<m}\binom{m+j-1}{j} = \tfrac12\binom{2m}{m}$ with $m=(n+1)/2$. That is $6$ for $\mathrm{MAJ}_3$, matching the familiar three-query tree. Recorded as an upper bound only: no matching lower bound is claimed here, the best easy one being $2^{(n+1)/2}$ from the fact that every leaf subcube has codimension $\ge (n+1)/2$. |
| Threshold total | \(O\!\big(\binom{n+1}{k}\big)\) putative | The counting tree, which reads $x_1,x_2,\dots$ and stops as soon as $k$ ones or $n-k+1$ zeros have been seen, has $\sum_{z\le n-k}\binom{k-1+z}{z} + \sum_{o<k}\binom{n-k+o}{o} = \binom{n}{k}+\binom{n}{k-1} = \binom{n+1}{k}$ leaves by the hockey-stick identity. Upper bound only: the best easy lower bound is $2^{\min\{k,\,n-k+1\}}$, from the fact that every leaf subcube has codimension at least $\min\{k,\,n-k+1\}$. |
| EXACT-HALF total | \(\Theta(2^n/\sqrt n)\) putative | Lower: $\mathrm{C}^1 = n$, so every $1$-leaf is a single point of the cube and the tree needs $\binom{n}{n/2}$ of them. Upper: the counting tree -- read $x_1,x_2,\dots$ and halt as soon as either count exceeds $n/2$ -- has $\binom{n}{n/2} + 2\binom{n}{n/2+1}$ leaves. Both ends are $\Theta(2^n/\sqrt n)$. |
| ODD-MAX-BIT total | \(n+1\) putative | Query $x_n, x_{n-1}, \dots$ and stop at the first $1$: a path with $n$ branchings, hence $n+1$ leaves. The all-zero input forces a root-to-leaf path of length $n$, so no smaller tree exists. |
| ADDRESS / multiplexer total | \(2^{k+1}\) putative | Each leaf-subcube is monochromatic, hence of codimension $\ge \mathrm{C}_{\min} = k+1$, hence of measure $\le 2^{-(k+1)}$; the leaves partition the cube, so there are at least $2^{k+1}$ of them. The natural tree achieves it: $2^k$ address paths, each ending in one table query. |
| Binary tree navigation total | \(2^k\) putative | Exactly. The walk tree is complete of depth $k$, giving $2^k$ leaves. For the lower bound: the walk is the unique minimal certificate, so every leaf's read-set contains one complete walk together with its final bit, and the $2^{k-1}$ walks times the $2$ values of the final bit need $2^k$ distinct leaves. |
| TRIBES total | \(2^{\Omega(n/\log n)},\ 2^{O(n\log\log n/\log n)}\) putative | Lower: the subcube of a $0$-leaf must contain a $0$ in each of the $s$ tribes, so it has codimension at least $s$ and measure at most $2^{-s}$; the $0$-leaves cover a set of measure $\Pr[f=0] \to 1/2$, so there are at least $2^{s-1}$ of them, and $s = \Theta(n/\log n)$. Upper: the natural tree reads one tribe at a time, stopping at the first $0$ inside a tribe, and its leaf count satisfies $T(j) = w\,T(j-1)+1$, giving $T(s) \le 2w^s = 2^{O(s\log w)} = 2^{O(n\log\log n/\log n)}$. The $\log\log n$ gap is left open. |
| AND-OR tree (depth 2) total | \(\Theta(n^n) = 2^{\Theta(\sqrt N\log N)}\) putative | Upper: the tree above has $S_j = n\,S_{j+1} + 1$ leaves for blocks $j..n$, i.e. $S_1 = (n^{n+1}-1)/(n-1) < \tfrac{n}{n-1}n^n$. Lower: the $n^n$ inputs with exactly one $1$ per block must reach distinct leaves, for if two of them differ in block $j$ then both of that block's $1$-positions are free in the common leaf-subcube, and zeroing the block stays inside it while flipping $f$ to $0$. So $n^n \le \mathrm{DTsize} \le \tfrac{n}{n-1}n^n$. Far above $2^{\mathrm{rank}} = 2^{n}$ and far below $2^{\mathrm{D}} = 2^{n^2}$. |
| NAND tree (balanced AND-OR formula) total | \(2^{\Theta(N)}\) putative | A rank-$r$ decision tree contains a complete binary branching of depth $r$ and so has $\ge 2^r$ leaves; with $\mathrm{rank} \ge N/4$ that is $2^{\Omega(N)}$, and $2^{\mathrm{D}} = 2^N$ is the ceiling. Exact minimisation gives $3, 7, 25, 409, 62833$ leaves at $d = 1,\dots,5$, i.e. $\log_2 \mathrm{DTsize} \approx 0.5\,N$. |
| Recursive MAJORITY-of-3 total | \(2^{\Theta(N)}\) putative | A rank-$r$ decision tree contains a complete binary branching of depth $r$, hence has $\ge 2^r$ leaves; with $\mathrm{rank} = \Omega(N)$ that gives $2^{\Omega(N)}$, and $2^{\mathrm{D}} = 2^N$ is the ceiling. Exact minimisation gives $6$ leaves at $d=1$ and $116$ at $d=2$. |
| Kushilevitz's function (iterated) total | \(2^{\Theta(N)}\) putative | A decision tree of rank $r$ contains a complete binary branching of depth $r$ and so has at least $2^{r}$ leaves; with $\mathrm{rank} \ge N/2$ that gives $\mathrm{DTsize} \ge 2^{N/2}$, and $2^{\mathrm{D}} = 2^{N}$ is the ceiling. (The weaker generic bound $2^{\mathrm{C}_{\min}}$ would only give $2^{N^{0.77}}$.) |
| Rubinstein's function total | \(2^{\Omega(\sqrt N)},\ 2^{O(\sqrt N\log N)}\) putative | Lower: $\mathrm{DTsize} \ge 2^{\mathrm{rank}} \ge 2^{n}$. Upper: the block-by-block tree satisfies $S_j = a + b\,S_{j+1}$ where the optimal gadget tree has $a+b = \tfrac{n}{2}(\tfrac n2+2)$ leaves (exactly $8, 15, 24$ at $n = 4,6,8$), so $S_1 = n^{O(n)}$. Not pinned: the truth is somewhere between $2^{\Theta(\sqrt N)}$ and $2^{\Theta(\sqrt N\log N)}$. |
| Ambainis-Sun function total | \(2^{\Omega(\sqrt N)},\ 2^{O(\sqrt N\log N)}\) putative | Lower: $\mathrm{DTsize} \ge 2^{\mathrm{rank}} \ge 2^{3k+2}$. Upper: reading the blocks in turn multiplies the gadget's optimal tree size (exactly $13$ at $k=1$ and $30$ at $k=2$, i.e. $\mathrm{poly}(k)$) once per block, giving $k^{O(k)}$. Not pinned between the two. |
| AND composed with NOT-EXACT-HALF total | \(2^{\Theta(N)}\) | Between $2^{\mathrm{rank}}$ and $2^{\mathrm{D}}$, both $2^{\Theta(n^2)}$ by the \(\mathrm{rank}(f)\) entry. |
| Pointer functions total | \(2^{\widetilde\Omega(\sqrt n)}\) | Variant $f_{2m,m}$: a decision tree of rank $r$ has at least $2^r$ leaves, so $\mathrm{DTsize}\ge 2^{\mathrm{rank}}$, and $\mathrm{rank}\ge\mathrm{C}_{\min}=\widetilde\Omega(\sqrt n)$ from the Prover-Delayer game. The ceiling is the trivial $2^{\mathrm{D}}=2^{\widetilde O(n)}$. EhrenfeuchtHaussler89 |
| Cheat-sheet functions total | \(\widetilde\Omega(n)\) | Squeeze: $\mathrm{D}\le\mathrm{DTsize}-1$, so $\mathrm{DTsize}=\widetilde\Omega(n)$. The much stronger $\mathrm{DTsize}\ge 2^{\mathrm{rank}}$ route is unavailable because $\mathrm{C}_{\min}$, and hence $\mathrm{rank}$, has no recorded floor here. |
| Low-sensitivity function from unambiguous certificates total | \(\widetilde\Omega(n^3)\) | Squeeze: $\mathrm{D}\le\mathrm{DTsize}-1$, so the tree needs at least $\widetilde\Omega(n^3)$ leaves. Only the trivial size bound is claimed -- the exponential lower bound one would expect is not established here. |
| Unambiguous-DNF / Alon-Saks-Seymour function total | \(\widetilde\Omega(n^2)\) | Squeeze: $\mathrm{D}\le\mathrm{DTsize}-1$ with $\mathrm{D}=\widetilde\Theta(n^2)$. The stronger $\mathrm{DTsize}\ge 2^{\mathrm{rank}}$ route is unavailable: $\mathrm{C}_{\min}=\widetilde O(n)$ is only an upper bound, so $\mathrm{rank}$ has no recorded floor. |
| Gilmer-Saks-Srinivasan functions total | \(2^{\Omega(n)}\) | A decision tree of rank $r$ has at least $2^r$ leaves, so $\mathrm{DTsize}\ge 2^{\mathrm{rank}}$, and the recorded $\mathrm{rank}=\Omega(n)$ (every input needs an $n$-bit certificate) gives an exponential size lower bound. The ceiling is the trivial $2^{\mathrm{D}}=2^{O(n^2)}$. EhrenfeuchtHaussler89 |
| Goos-Pitassi-Watson partition-number function total | \(2^{\widetilde\Omega(\sqrt n)}\) | A decision tree of rank $r$ has at least $2^r$ leaves, so $\mathrm{DTsize}\ge 2^{\mathrm{rank}}$ and the recorded $\mathrm{rank}=\widetilde\Omega(\sqrt n)$ gives an exponential size floor. The ceiling is the trivial $2^{\mathrm{D}}=2^{\widetilde O(n)}$. EhrenfeuchtHaussler89 |
| Goos-Jayram-Pitassi-Watson function total | \(2^{\widetilde\Omega(n^{1/3})}\) | A decision tree of rank $r$ has at least $2^r$ leaves, so $\mathrm{DTsize}\ge 2^{\mathrm{rank}}$ and the recorded $\mathrm{rank}=\widetilde\Omega(n^{1/3})$ gives an exponential size floor. The ceiling is the trivial $2^{\mathrm{D}}=2^{\widetilde O(n^{2/3})}$. EhrenfeuchtHaussler89 |
| Ambainis' exact-quantum function total | \(2^{\Omega(2.3028^d)}\) | A decision tree with $L$ leaves has rank at most $\log_2 L$, so $\mathrm{DTsize}\ge 2^{\mathrm{rank}}\ge 2^{\mathrm{C}_{\min}}=2^{\Omega(2.3028^d)}$, against the ceiling $2^{\mathrm{D}}=2^{3^d}$. Doubly exponential in the asymptotic variable, hence recorded in a form the growth parser does not read. |
| FORRELATION partial | \(2^{\Theta(n)}\) | At least $2^{\mathrm{C}_{\min}}$ and at most $2^{\mathrm{D}+1}$, and $\mathrm{C}_{\min} = \Theta(\mathrm{D}) = \Theta(n)$. Unlike \(\mathrm{DJ}_n\), no small tree exists: the promise here has no cheap side. |
| Deutsch-Jozsa partial | \(\Theta(N)\) putative | The tree above has one leaf per stopping point on each of its two branches, so $O(N)$; and a tree of depth $d$ has more than $d$ leaves, so $\Omega(N)$ from $\mathrm{D} = N/2+1$. |
| Bernstein-Vazirani partial | \(2^n\) putative | Every leaf subcube has codimension $\ge \mathrm{C}_{\min} = n$, so there are at least $2^n$ leaves; and querying $e_1, \dots, e_n$ gives exactly $2^n$. |
| Dense marked bit partial | \(\Theta(n)\) putative | Upper: the caterpillar above has $O(n)$ leaves. Lower: a tree with $L$ leaves has depth $\le L-1$, and the depth is at least $\mathrm{D} = n/2+1$. |
| Unstructured search (relation) relation | \(n+1\) putative | Query $x_1, x_2, \dots$ and stop at the first $1$: $n+1$ leaves. And the all-zero input forces a root-to-leaf path of length $n$, whose $n$ branchings already create $n+1$ leaves. |
| FIND-1 under a density promise relation | \(\Theta(n)\) putative | The caterpillar has one leaf per stopping point, so $O(n)$; and a tree of depth $d$ has more than $d$ leaves, so $\Omega(n)$ by $\mathrm{D} = n/2+1$. Unlike \(\mathrm{ApproxHW}\) and \(\mathrm{Search}(\varphi)\), the deterministic hardness here is entirely depth and not at all size. |
| Approximate Hamming weight relation | \(2^{\Theta(n)}\) putative | Each leaf subcube must force a valid answer, hence has codimension $\ge (1-2\varepsilon)n$ by the certificate bound above, hence contains at most $2^{2\varepsilon n}$ inputs; so at least $2^{(1-2\varepsilon)n}$ leaves are needed, and $2^n$ suffice. This is the worst-case analogue of the $\exp(\widetilde\Omega(n^{1/4}))$ pseudo-deterministic size bound of [CDM23]. |
| SearchCNF relation | \(2^{\Theta(n)}\)· | Decision-tree size for the search problem equals tree-like resolution size, and the size-width tradeoff of [BenSassonWigderson01] with the $\Omega(n)$ width bound gives $2^{\Omega(n)}$ for random $k$-CNFs; $2^n$ is the trivial ceiling. Compare $\mathrm{R}=O(1)$: no bounded-error algorithm needs to know anything about $\varphi$ beyond one clause. BenSassonWigderson01 |
| Gap-Majority partial | \(2^{\Theta(n)}\) putative | Every leaf subcube has codimension $\ge \mathrm{C}_{\min} = \Theta(n)$, giving $2^{\Omega(n)}$ leaves; and $\mathrm{DTsize} \le 2^{\mathrm{D}}$. |
| Gap-Majority at constant gap partial | \(2^{\Theta(n)}\) putative | Every leaf subcube has codimension $\ge \mathrm{C}_{\min} = \Theta(n)$; and $\mathrm{DTsize} \le 2^{\mathrm{D}}$. |
| Parity-labelled FIND-1 partial | \(\Theta(n)\) putative | The caterpillar "query odd positions until the first $1$" has one leaf per stopping point, so $O(n)$; and a tree of depth $d$ has more than $d$ leaves, so $\Omega(n)$ by $\mathrm{D} = n/4+1$. As at \(\mathrm{Find1}_{\ge n/2}\), the deterministic hardness is depth, not size. |
| Ambainis-Belovs function partial | \(\Omega(n^{2/3})\) | $\mathrm{Q}_{2/5}(f) = O(\sqrt{\mathrm{DTsize}(f)})$, so $\mathrm{DTsize} = \Omega(\mathrm{Q}^2) = \Omega(n^{2/3})$. This is one of the few places where a degree-blind lower bound propagates: the tree-size bound goes through $\mathrm{Q}$, not through $\deg$. |
| Ben-David-Kundu total search problems relation | \(2^{\widetilde\Omega(\sqrt n)}\)? putative | A tree of depth $d$ has more than $d$ leaves, so this only says $\mathrm{DTsize} > \mathrm{D}$; the exponential form follows because every leaf must force a valid output, and $\mathrm{C} = O(\log^6 n)$ certificates cannot be reached in fewer than $\mathrm{D}$ queries on the hard inputs. |
| Yamakawa-Zhandry problem relation | \(2^{\Omega(n)}\) | A tree of depth $d$ has more than $d$ leaves, so $\mathrm{DTsize} > \mathrm{D} = 2^{\Omega(n)}$. |
| Surjectivity total | \(\Omega(2^{n/\log n}),\ O(2^n)\) putative | Lower: a tree with $L$ leaves has one at depth $\le \log_2 L$ (Kraft), and a leaf at depth $t$ is a certificate of size $t$, so $\log_2 L \ge \mathrm{C}_{\min} = \Theta(n/\log n)$. Upper: the complete tree. The $\log n$ in the exponent is exactly the gap between $\mathrm{C}_{\min} = \Theta(N)$ and $\mathrm{D} = n = N\log_2 R$, i.e. the fact that a $0$-certificate spends one bit per slot rather than $\log R$. |
| $k$-distinctness total | \(2^{\Theta(n\log n)}\)· putative | For $q\ge n$ (so that the all-distinct inputs exist) every $0$-input needs all $n$ symbols read, since $\mathrm{C}^0=n$, so distinct $0$-inputs end at distinct leaves; the $n!$ orderings of $n$ fixed distinct values already give $\mathrm{DTsize}\ge n!=2^{\Theta(n\log n)}$. The ceiling is $q^n$, which matches for $q=\mathrm{poly}(n)$. |
| Triangle finding total | \(2^{\Theta(m^2)}\) putative | Every $0$-input needs all $\binom m2$ edges read, since $\mathrm{C}^0=\binom m2$, so distinct triangle-free graphs end at distinct leaves. The $2^{m^2/4}$ bipartite graphs on a fixed balanced vertex split are all triangle-free, so $\mathrm{DTsize}\ge2^{m^2/4}$; the ceiling is $2^{\binom m2}$. |
| Welded trees relation | \(\Omega(4^n)\) putative | Answer counting. Each leaf of a tree is labelled with a single vertex name, and for every one of the $2^{2n}$ names there is a legal instance whose EXIT carries that name, so instances with different EXIT names must reach different leaves. Hence $\mathrm{DTsize}\ge2^{2n}=4^n$ -- the same $\Theta(4^n)$ that makes the non-adaptive complexity trivial. |
| Local search on the hypercube relation | \(\Omega(2^n)\) putative | Answer counting: for every vertex $v$ of the cube the table $f(x)=|x\oplus v|$ has $v$ as its unique local minimum, so the $2^n$ vertices force $2^n$ distinct leaves. |
| Local search on the grid relation | \(\Omega(k^d)\) putative | Answer counting: for every cell $v$ the table $f(x)=\|x-v\|_1$ has $v$ as its unique local minimum, so all $N=k^d$ cells force distinct leaves. |
| Fourier fishing relation | \(2^{\Theta(N)}\) putative | Every leaf is deep, so the tree is wide. A tree with $L$ leaves has one at depth $\le \log_2 L$ (Kraft), and a leaf at depth $t$ is a subcube on which one fixed $z$ is output, i.e. a certificate of size $t$; by the $\mathrm{C}$ row every certificate has size $\ge N/2$, so $\log_2 L \ge N/2$. Upper: the complete tree, $2^N$ leaves. Contrast $\mathrm{Q} = 1$: this is a $2^{\Omega(N)}$-versus-one-query gap, far past the $\mathrm{Q}_{2/5} = O(\sqrt{\mathrm{DTsize}})$ ceiling (\(\mathrm{DTsize}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), which of course only bounds $\mathrm{Q}$ from above. |
| Ordered search partial | \(n+1\) putative | Exactly. Lower: the promise inputs reaching a fixed leaf are those $k$ compatible with the answers along the path, which is an interval of $k$; consecutive $k$ have opposite parity, so on the decision version $\mathrm{OS}^{\oplus}_n$ that interval must be a singleton, and there are $n+1$ inputs. Upper: binary search has exactly $n+1$ leaves. Consistent with the Ehrenfeucht-Haussler bound: a rank-$1$ tree of depth $n$ has at most $n+1$ leaves, and the comb attains it. |
| Tseitin search on an expander relation | \(2^{\Theta(n)}\) | Decision-tree size for the search problem is tree-like resolution size, and [Urquhart87] gives $2^{\Omega(n)}$ on an expander; $2^n$ is the ceiling. Urquhart87 BenSassonWigderson01 |
| Inner product mod 2 total | \(2^{\Theta(n)}\) putative | Upper: the natural tree has three continuations per index ($x_i=0$; $x_i=1,y_i=0$; $x_i=1,y_i=1$), so $3^{m} = 3^{n/2}$ leaves. Lower: every leaf-subcube is monochromatic, hence of codimension $\ge \mathrm{C}_{\min} = n/2$, so there are at least $2^{n/2}$ of them. |
| Minsky-Papert one-in-a-box total | \(\Theta(m^{2m})\) putative | The tree above has $L_k = m^2 L_{k-1} + 1$ leaves after $k$ boxes, i.e. $\sum_{j=0}^{m} m^{2j}$ leaves. Matching lower bound: the $m^{2m}$ inputs with exactly one $1$ per box reach pairwise distinct leaves, since a monochromatic-$1$ subcube containing two of them would leave both witnesses of some box free and hence contain an input with that box empty. So $m^{2m} \le \mathrm{D}_{\mathrm{size}} < m^{2m}(1 + 2m^{-2})$. Verified by exhaustive search at $(m,\,\text{box size}) = (2,4)$, where both sides give $21$. |
| Sink of a tournament total | \(2^{\Theta(m)} = 2^{\Theta(\sqrt N)}\) | Sandwiched: every leaf-subcube is monochromatic, hence of codimension $\ge \mathrm{C}_{\min} = m-1$, so $\mathrm{DTsize} \ge 2^{m-1}$; and $\mathrm{DTsize} \le 2^{\mathrm{D}} = 2^{O(m)}$. |
| Scorpion graphs total | \(2^{\Theta(m)} = 2^{\Theta(\sqrt N)}\) | Sandwiched: every leaf-subcube is monochromatic, hence of codimension $\ge \mathrm{C}_{\min} = m-1$, so $\mathrm{DTsize} \ge 2^{m-1}$; and $\mathrm{DTsize} \le 2^{\mathrm{D}} = 2^{O(m)}$. Note $\log_2\mathrm{DTsize} = \Theta(\sqrt N)$ while there are $N$ variables -- the tree is exponentially smaller than the truth table. |