Space complexity of boolean circuit evaluation
This general question is captured by the concept of graph pebbling. Orient the edges of the circuit so that they point away from the leaves and toward the root. A pebbling of the graph is a series of moves, in the course of which pebbles are added to and removed from vertices (at most one pebble per vertex!), according to the following rules:


A pebble can always be removed.
A node $v$ can be pebbled (we can add a pebble to it) if all nodes $w$ such that there is an edge $w \to v$ are pebbled.


The goal is to pebble the root, and what we want to minimize is the maximum number of pebbles on the board. This minimum is called the pebbling number of the circuit.

If a circuit has pebbling number $p$, then it can be evaluated using roughly $p$ bits of memory. The idea is that pebbling a node corresponds to computing the its value, which is possible since all of its children are pebbled as well.

All of the above concerns the case in which the circuit is given ahead of time, and the goal is to construct a strategy to evaluate it on an unknown input. However, the same general approach can also be used to solve your problem, using the fact that the pebbling number of the complete binary tree of depth $D$ is $O(D)$. For more on pebbling, see Nordström's survey.

Finally, let me mention that the circuit evaluation problem is $\mathsf{P}$-complete. This means that assuming $\mathsf{L} \neq \mathsf{P}$, it is not possible to evaluate arbitrary circuit in logarithmic space. In contrast, the formula evaluation problem is in $\mathsf{ALOGTIME}$ (i.e., uniform $\mathsf{NC^1}$), and so in $\mathsf{L}$. This is due to important work of Buss.