patternMinor
Level-order traversal of a balanced tree, with no parent pointers in $\mathcal o(n)$ space
Viewed 0 times
orderspacelevelwithparentbalancedpointersmathcaltreetraversal
Problem
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:
-
is there a algorithm for traversing a balanced tree without parent-pointers in linear-time, and logarithmic space?
-
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).
-
Or more generally, linear time, but sub-linear space?
Also, no cheating, you cannot alter the tree :)
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:
-
is there a algorithm for traversing a balanced tree without parent-pointers in linear-time, and logarithmic space?
-
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).
-
Or more generally, linear time, but sub-linear space?
Also, no cheating, you cannot alter the tree :)
Solution
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.
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.
Context
StackExchange Computer Science Q#49270, answer score: 2
Revisions (0)
No revisions yet.