6
$\begingroup$

My question spawns from this question. The question is straightforward:

Can we find whether there exist 2 values in a balanced binary search tree where their sum equals a given target value?

Now the constraints:

  1. Constant additional space in regards to $n$, the size of the tree. By this I mean you can use a constant number of $O(\log n)$ bit words however you wish. Assume references to nodes also take $\log n$ bits to store.

  2. Read-only access to the tree. No modifications are allowed. This prevents a threaded traversal.

  3. A node n has the following attributes: n.left, n.right, n.value. This means we have no access to a node's parent. This prevents a successor and predecessor traversal.

  4. The algorithm must run in worst-case linear time in regards to $n$, the size of the tree.

It's worth noting that if we remove any one of the four constraints, we can satisfy the the other three relatively easily.


My initial thought is that this is not possible. Simply because we can have no memory of where we are in the tree when traversing it.

We could however implement a successor and predecessor in-order traversal using binary searches to find successors and predecessors. This would take $O( n \log n)$.

Another thought was that we could use a non-deterministic algorithm. Possibly a Monte Carlo algorithm with repetition or a Las Vegas algorithm. This randomized algorithm could be used to do a random walk along one path, then have another path search for a compatible node based on the random walk's nodes. I'm not entirely sure if this would work, but these are just some thoughts.

If this is indeed not possible, as I am suspicious, I would also be interested in the following additional modification:

  • The algorithm must run in average-case linear time.
$\endgroup$
  • 2
    $\begingroup$ Just to be sure: 1) prevents also the recursion? So we cannot cheat having the parent into search function? $\endgroup$ – Evil Jul 1 '17 at 22:48
  • 1
    $\begingroup$ @Evil, correct, recursion would involve using $\log n$ stack space. That breaks the constraint. $\endgroup$ – ryan Jul 1 '17 at 23:02
  • $\begingroup$ @D.W. I've updated that section slightly. Could you elaborate on this in-order traversal? $\endgroup$ – ryan Jul 2 '17 at 2:43
  • $\begingroup$ @ryan, Oops, when I went to write up the idea that I thought I had, I realized it doesn't work. My mistake. Thanks for the clarification about the model of computation -- very helpful! $\endgroup$ – D.W. Jul 2 '17 at 2:49
  • $\begingroup$ @D.W. if you don't mind sharing, what was the idea and why doesn't it work? $\endgroup$ – ryan Jul 2 '17 at 2:56
5
+50
$\begingroup$

I don't know how to do this is in $O(n)$ time and $O(1)$ space, but I can show you how to do it in $O(n)$ time and $O(\lg \lg n)$ space. In particular, given any tree of depth $O(\lg n)$, I'll show how to do an in-order traversal in $O(n)$ time and $O(\lg \lg n)$ space. That will be enough to solve this problem.

Warmup

Let me first establish some notation. At any point in the traversal, we'll currently be at some leaf node $x_1$. Let $x_1,x_2,x_3,\dots,x_d$ be the nodes on the path from $x_1$ to the root (so $x_1$ is the leaf and $x_d$ is the root of the tree), where $d$ denotes the depth of the tree. Note that since the tree has depth $O(\lg n)$, it follows that this sequence has length $O(\lg n)$.

For convenience, I'll assume that the tree is a complete binary tree, i.e., all leaves are at the same depth. This simplifies explanation of the main ideas. All of the techniques here generalize to an arbitrary binary tree, as long as its maximum depth is $O(\lg n)$.

An easy way to do a traversal would be to keep track of the entire sequence $x_1,x_2,x_3,\dots,x_d$. When you want to find the successor, you update the entire sequence. For instance, if $x_1$ is the left child of $x_2$, this involves updating just $x_1$ to its right sibling. If $x_1$ is the right child of $x_2$ and $x_2$ is the left child of $x_3$, this involves updating $x_1$ and $x_2$. And so on. Notice that as we repeatedly compute the successor, the first parts of the sequence get updated more often: $x_1$ changes every time, $x_2$ changes half of the time, $x_3$ changes $1/4$ of the time, and so on. This gives an $O(n)$ time traversal (since $1 + 1/2 + 1/4 + \cdots = O(1)$), but it requires $O(\lg n)$ space.

The main attraction

Our improvement will be to store only part of that sequence: we'll store $x_1,x_2,x_4,x_8,\dots,x_k$ (where $k=2^{\lfloor \lg d \rfloor}$). In other words, we're only storing the power-of-two-indexed elements of the path from the current leaf to the root. Since $d=O(\lg n)$, we're only storing $O(\lg \lg n)$ elements of the sequence.

When we want to find the successor, we might need to update one or more of these elements. As we repeatedly iterate compute successors, the early parts change more often: $x_1$ always changes, $x_2$ changes $1/2$ of the time, $x_4$ changes $1/2^3$ of the time, $x_8$ changes $1/2^7$ of the time, $x_{16}$ changes $1/2^{15}$ of the time, and so on. How do we do the updates? To see if $x_2$ needs to change, we go down from $x_2$ to $x_1$ to find the successor to $x_1$. If $x_2$ doesn't need to change, we're done. Otherwise, we go down from $x_4$ to $x_2$ to find the successor to $x_2$ (at the same height as $x_2$). And so on. When $x_{2^i}$ changes, we go down from $x_{2^{i+1}}$ to $x_{2^i}$ to compute the successor to $x_{2^i}$ at the same height, and this takes $2^i$ steps of computation since we have to traverse $2^i$ levels of the tree; this happens for a $1/2^{2^i-1}$ fraction of the successor operations. Taking all of that into account, the amortized amount of work we do per successor operation is

$$1 + {2 \over 2} + {4 \over 2^3} + {8 \over 2^7} + {16 \over 2^{15}} + \cdots = O(1).$$

This yields an in-order traversal that takes $O(n)$ time and $O(\lg \lg n)$ space.

Bonus answer

As an extra bonus, I'll show how to do an in-order traversal in $O(n \lg^* n)$ time and $O(\lg^* n)$ space. $O(\lg^* n)$ "might as well be constant" for all practical purposes, so maybe this is of interest.

The construction is a small modification of the scheme I gave above. Define $a_1,a_2,a_3,\dots$ by $a_1 = 1$ and $a_{i+1} = 2^{a_i}$. Now, instead of storing the whole sequence $x_1,\dots,x_d$, we'll store just the elements $x_{a_1},x_{a_2},x_{a_3},\dots,x_{a_\ell}$, where $\ell= \lg^* d = \lg^* (\lg n)$. Notice that $x_{a_i}$ changes for a $1/2^{a_i-1}$ fraction of the successor operations, and when it does change, we do $a_{i+1} - a_i$ work. Therefore, the amortized time per successor operation is

$$T = \sum_{i=1}^\ell {a_{i+1} - a_i \over 2^{a_i-1}}.$$

With a bit of manipulation we can show

$$T \le \sum_{i=1}^\ell {a_{i+1} \over 2^{a_i-1}} = \sum_{i=1}^\ell {1 \over 2} = \ell/2 = O(\lg^* (\lg n)) = O(\lg^* n).$$

Therefore, a traversal of the entire tree can be done $O(n \lg^* n)$ time, using $O(\lg^* n)$ time.

$\endgroup$
  • $\begingroup$ This is an interesting approach I hadn't thought of before. Yes this question is difficult to answer in my opinion, but that's part of what makes it interesting! $\endgroup$ – ryan Jul 2 '17 at 18:37
  • $\begingroup$ @ryan, I edited my answer to add a bonus scheme. $\endgroup$ – D.W. Jul 3 '17 at 1:28
  • $\begingroup$ Great approach, I like the $O(\lg^* n)$ bonus solution. I wish I could accept this because it is a great insight, but I really am wanting that constant space & linear time solution (or disproof of its existence). $\endgroup$ – ryan Jul 3 '17 at 5:05
0
$\begingroup$

This is an attempt to prove a lower bound of $\Omega(n \log n)$ for solving the problem using any comparison based algorithm under the first 3 constraints. (Feel free to point out flaws if you notice them)

There are two core concepts to the proof.

  1. The algorithm must visit all non-root nodes.

  2. Cost of visiting all non-root nodes is $\Omega(n \log n)$.


Must Visit All Non-Root Nodes

The Tree Structure

The adversary will maintain a perfect binary search tree. The approach will be similar to @jschnei's reduction here.

Let the tree be of size $n = 2^k - 1$.

We will index the nodes in ascending order about the root for convenience (e.g. $x_0 = $root, $x_{-\frac{n-1}{2}} = $min, $x_{+\frac{n-1}{2}} = $max). We then have a simple way to define node values:

$$x_i = i \cdot 2$$

For example, let's say we have a tree of size $n = 7$. It will look like the following:

BST

The Analysis

The adversary will establish the target value as $t = 1$. The adversary will accept queries of the following format:

$$x_i + x_j \text{ COMP } t \quad \text{ COMP }= \{<, =, >\}$$

The adversary will maintain a list of all nodes that have been queried so far. Until every node besides the root has been queried, it is undecided whether or not a pair of nodes will sum to $t = 1$ because if a node has not been checked we could either add $1$ to it and the problem would be satisfied or leave it as is and the problem would not be satisfied.

It is clear to see this will require visiting all nodes except the root, inevitably ending up in the problem not being satisfied. There is no need to visit the root if we have already checked all other pairs because the root is one value not a pair of values and thus it won't matter if it sums to $1$, the problem will still not be satisfied.


Visiting All Non-Root Nodes Takes $\Omega( n \log n)$ Time

We can easily prove this by proving that visiting all leaf nodes takes $\Omega(n \log n)$ time.

Let's first note some things:

  1. The algorithm has limited history. We can assume at any point the algorithm has memory of exactly $k$ nodes.

  2. A node that has not been traversed yet can not be one of the $k$ nodes.

  3. The algorithm can not traverse up the tree. It can however bounce back to any of the $k$ nodes it has previously stored.

At any rate, it is safe to assume we can always create a tree large enough where the $k$ nodes the algorithm has in memory becomes insignificant and the amortized cost of visiting a leaf node will always be $\Omega(\log n)$. Intuitively this makes sense but I'll try to give an informal proof below.

We will assume $k \ll \log_2 n$. Then at any point in the traversal to a leaf node let's assume the $k$ memory cells contain a set of nodes $y \subset x$ along the path to the leaf. We will include the root node and leaf node in $y$ as an assumption, because if you weren't keeping track of the root you could easily be lost and the other assumption is that we're currently at a leaf. In order from leaf to root we have the $k$ memory cells as $\{y_1, y_2, \dots y_k\}$. Let's also define $d(y_i, y_j)$ to be the positive difference in depth between two nodes. Then we have:

$$ k \in O(1) \implies \exists y_{i-1}, y_i \in y \text{ such that } d(y_{i-1}, y_i) = \Omega(\log n)$$

This is obvious because in the best case, the $k$ memory cells are evenly spread about the path to the leaf and then $d(y_{i-1}, y_i) = \frac{\log n}{k} = \Omega(\log n)$. In any other case, at least one of the stepwise pairs are spread greater than $\frac{\log n}{k}$.

We then have that for a pair $(y_{i-1}, y_i)$ on the path whose depth difference is proportional to $\log n$, getting to any leaf in the subtree rooted at $y_{i-1}$'s sibling will clearly take $\Omega(\log n)$ time. We can extrapolate this for the new (if indeed new) dispersion of $i-1$ memory cells in this new subtree that there will be some instance of moving to a new subtree (whether it be within this subtree or outside) that will also take $\Omega(\log n)$ even if it is just some fraction of $\log n$. Therefore the total amortized cost of visiting each leaf node will be some proportion of $\log n$, also $\Omega(\log n)$. Thus visiting all leaf nodes will be some proportion of $n \log n$.

The implications of all this is that we must take $\Omega( n \log n)$ time to satisfy the first 3 constraints.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.