# Level-order traversal of a balanced tree, with no parent pointers in $\mathcal o(n)$ space

Assuming you have a balanced tree, without parent-pointers, with $n$ nodes, and a height $H = \mathcal O(\log n)$.

I know you can traverse the tree in level order in $\mathcal O(n)$ time using a queue. However, even in a balanced tree, the queue can grow to $\mathcal O(n)$ in size.

So the best I came up with is essentially to in/pre/post order traverse the tree in $H$ passes, one for each level in the tree, and simply filter the visits to the level for that pass. This gives an algorithm with $\mathcal O(n\cdot H ) = \mathcal O(n \log n)$ runtime and $\mathcal O(H) = \mathcal O(\log n)$ space.

The question is:

1. is there a algorithm for traversing a balanced tree without parent-pointers in linear-time, and logarithmic space?

2. Or at least, in $\mathcal o(n\log n)$ time and $\mathcal O(\log n)$ space (i.e a better result than my naive algorithm).

3. Or more generally, linear time, but sub-linear space?

Also, no cheating, you cannot alter the tree :)

• Too bad we can't cheat. Rewiring the tree to a first-child-next-node-on-level representation would work in $O(1)$ memory. Hm, can we reset to the original pointer structure with as little memory?
– Raphael
Nov 9, 2015 at 23:35
• But isn't this the same as generating the (binary) sequence $\lambda$ (for root), 0, 1, 00, 01, 10, 11, 000, 001, 010, ... up to $\log n$ bits? Which for each fixed $k$ bits is of the order $2^k$ steps (as far as I remember). And then in total $2^0+2^1+\dots+2^{\log n}$. Nov 10, 2015 at 0:08
• @HendrikJan I'm not sure I'm understanding correctly, but does that not assume a full tree? A sparse tree might be missing a whole bunch of those. Nov 10, 2015 at 3:53
• You are right, but missing branches can be skipped. Just follow the path along the edges. The point is wether the complexity analysis is correct. But I remember that binary counting up to a number is in linear time, and your path along the tree seems to follow the same schedule. Nov 10, 2015 at 4:01
• @HendrikJan so again, maybe i'm misunderstanding, 1) having the number doesn't immediately translate to the path; getting from a number to the node can take $\mathcal O(\log n)$ time (the length of the number or in other words, the depth of the node). 2) It is true, that you can iterate through the tree like this without retracing from the root each time, and the number (essentially the node path) is $\mathcal O(\log n)$ space, but my intuition tells me that going up and down the tree (to get the "next" node) will take in total $\mathcal O(n\log n)$ time, no better than my naive algorithm. Nov 10, 2015 at 7:28

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.

• Right, I thought of this same thing just without the node-path representation (but I was always aware of that as a representation), but it is the last part that concerned me as well. Also, using the bitstring as a node-path still requires that "dereferencing" operation, which is a logarithmic operation (but is easy to alleviate by doing the exact same thing directly with the nodes). However, as I said, that last part needs to be fleshed out :), I'm not 100% convinced that it is indeed linear. Nov 10, 2015 at 8:20
• If this works, then it is a better solution than what I actually in mind!! I was implicitly imagining that the path would be on the stack. Nov 10, 2015 at 12:42
• I asked this in ##cs on freenode and got it down to a succinct method and proof of the last part. Framing the iteration as: like my naive algorithm, do an iterated depth-first traversal, each iteration go down to level $k$, but stop there. This extra condition of stopping at the level seems to do the trick: the last level traversed has $\mathcal O(n)$ nodes traversed, the 2nd last has $\mathcal O(\frac n 2)$ and it halves for each lesser level, giving us a geometric series of no more than $(2n \cdot c) \in \mathcal O (n)$ nodes visited. Nov 11, 2015 at 13:16