Level-order traversal of a balanced tree, with no parent pointers in $\mathcal o(n)$ space
Let's start by considering the case of a full tree (depth $\lg n$, contains exactly $n$ leaves, where $n$ is a power of two).  It's possible to build an algorithm for this case with space complexity $O(\lg n)$ and total running time $O(n)$.

In particular, Hendrik Jan describes an elegant algorithm whose running time is $O(n)$.  Let me flesh out the details.  Consider a $\lg n$-bit counter, whose value is stored in binary, and that supports one operation: Increment (adds one to the counter).  How many bits needed to be flipped by each invocation of the Increment operation?   The answer is $\lg n$ in the worst case (when you increment from $0111 \cdots 1$ to $1000 \cdots 0$), but a standard analysis shows that the amortized number of bit-flips is $O(1)$ -- the amortized analysis is a standard exercise in many algorithms textbooks.

Note that you can treat any bit-string $x$ of length $\le \lg n$ bits as a specification of a path from the root of the tree to some node $n(x)$ ($0$ means go left; $1$ means go right; the most significant bit is the first branch taken in the path; the least significant bit is the last branch).
Suppose the $\lg n$ bits stored in the counter are denoted $b_1,\dots,b_{\lg k}$.  Treat the bit-string stored in the counter as a specification of a path to a leaf.  Also, for each index $i$, store a pointer to the node $n(b_1 \cdots b_i)$, i.e., the node reached by following the path that corresponds to the first $i$ bits in the counter (the $i$ most significant bits).  This takes $O(\lg n)$ space.

Now we're going to repeatedly increment the counter, and update the pointers.  We only need to update a pointer when its corresponding bit flips: e.g., if $b_i$ changes, we'll need to update the pointer $n(b_1 \cdots b_i)$.  This update can be done in $O(1)$ time, by using the pointer to $n(b_1 \cdots b_{i-1})$ and then looking at its left or right child (depending on whether $b_i=0$ or $b_i=1$ after the update).  Importantly, whenever bit $i$ flips, so do all of the bits $i,i+1,i+2,\dots,\lg n$, so all of the pointers will be updated as necessary.  Thus, at every point in time all $\lg n$ pointers are correct.

What's the running time?  We only update a pointer when its corresponding bit changes.  Each time we update a pointer, we do $O(1)$ work.  Therefore, the total number of operations is equal to the total number of bits that have changed, as we increment the counter from $1$ to $n$.  But now it's a standard result that the amortized running time of the Increment operation is $O(1)$ bit flips: i.e., you can increment the counter $n$ times, at the cost of a total of $O(n)$ bit flips.  Therefore, the running time of this algorithm is $O(n)$, and the space complexity is $O(\lg n)$.  The constants hidden by the big-O notation are relatively small: e.g., the total number of bit flips is $\le 2n$, so you'll follow about $2n$ child pointers, and you only need space for $\lg n$ pointers.



What if the tree is not full?  In other words, maybe the tree has $n$ leaves and depth $c \lg n$.  Then a bunch of subtrees are missing.  However, I think it is possible to just skip over them as you increment the counter.  Therefore, it looks to me like the total running time should remain $O(n)$ for this case, and the space complexity will be $O(\lg n)$.  I confess I haven't checked the details of this part carefully, but it looks like it should work out.