2
$\begingroup$

Prove that given a number we can find whether there're 2 elements in a red/black tree that their sum equals that number in $\Theta(n)$ time and constant space.

The original problem appears here, however the solution uses $\lg n$ space. A problem in my course required adjusting the algorithm such that we use constant space.

I thought of the following algorithm:

MyAlgorithm(root, num)
    min<-findMin(root)
    max<-findMax(root)
    while(min.key <= max.key && min != max)
        if((min.key + max.key)=num) return true
        if((min.key + max.key) < num)
            min<-successor(min)
        else
            max<-predeccessor(max)
    return false

According the CLRS book both predeccessor() and successor() functions time complexity depends on tree height which is $O(\lg n)$ in our case since red-black tree is balanced.

However, we have the while loop which theoretically can run almost n times.

For example, because the algorithm above is equivalent to searching for the number num in a sorted array, say we have this array and num<-3: $$ 1,2,3,4,5,6,7,8,9,10 $$ In this case we'll call predecessor(max) $8$ times which is almost $\Theta(n)$ or $\Theta((n-2)\lg n)=\Theta(n\lg n)$ asymptotically.

Am I wrong in my conclusions? How can I prove that the time complexity is indeed $\Theta(n)$?

$\endgroup$
  • 1
    $\begingroup$ 1. Please credit the original source of the problem. 2. Do you allow modifying the tree? 3. If only we had a way to do in-order traversal in constant space, we could apply cs.stackexchange.com/q/13585/755. Hmm. It's just possible it might be worth your time to try searching on that topic. $\endgroup$ – D.W. Jun 30 '17 at 19:46
  • $\begingroup$ @D.W. we cannot modify the tree. The post cs.stackexchange.com/questions/13585/… doesn't nearly have the restrictions that I have in the post, I don't really see the connection. $\endgroup$ – Yos Jun 30 '17 at 19:52
  • $\begingroup$ Can you clarify precisely what constant space means? Do you mean a constant number of memory cells, where each memory cell can hold a $\lg n$-bit number or a pointer into the tree? Do you mean a constant number of bits of memory? The former is probably the natural meaning. The latter is unlikely to be what you mean -- that isn't even enough to store a pointer to a single node in the tree. If the former, then you have $O(\lg n)$ bits -- can you think of any way to do an in-order traversal, if you were able to store $O(\lg n)$ bits? $\endgroup$ – D.W. Jun 30 '17 at 20:41
  • $\begingroup$ @D.W. such details were not mentioned in the original problem, all that was said was "constant space". $\endgroup$ – Yos Jun 30 '17 at 20:46
  • 1
    $\begingroup$ You said you saw the "original problem" somewhere else. Where? Was it in a book? A course? A programming contest? I encourage you to edit the question to tell us where you encountered the problem and provide credit to the place where you originally saw the problem. I'm not sure what post you are referring to. I'm talking about the statement of the problem, not your algorithm, not your code. $\endgroup$ – D.W. Jul 1 '17 at 1:39
2
$\begingroup$

So we are given a binary search tree $T$ (we, however, do not require it to be balanced). Also we are given an integer; let's call it target_number. We wish to query whether there are two distinct nodes in $T$ such that the sum of their values equals target_number. In order to do that, we need two functions: get_successor(x) and get_predecessor(x). Given a node x get_successor(x) returns the tree node whose value is larger than that of x and is the smallest such value. The definition of get_predecessor(x) is symmetric.

The algorithm is now (as in your question): point to the minimum node, and point to the maximum node. Compute the sum $S$ of the nodes pointed by the two pointers. If $S$ is less than the target number, move left pointer to its successor node. If $S$ is greater than the target number, move right pointer to its predecessor node. Otherwise, we have a match and return true.

query(root, target_number)
    left_finger  = the minimum node of the entire tree rooted at root
    right_finger = the maximum node of the entire tree rooted at root

    while left_finger != nil and right_finger != nil and left_finger != right_finger
        tentative_sum = left_finger.value + right_finger.value
        if tentative_sum < target_number
            left_finger = get_successor(left_finger)
        else if tentative_sum > target_number
            right_finger = get_predecessor(right_finger)
        else
            return true
    return false

Next, we need to give a strong argument that it runs, in fact, in $\Theta(n)$. Take a look at operation get_successor: If you start from the minimum node and visit the entire tree in successor order, you do $\Theta(n)$ work regardless the fact that get_successor runs in worst case $\mathcal{O}(\log n)$, and that is why: you visit each node at most three times: from the parent, returning from the left child and returning from the right child; we spend constant time at each node.

As you can see from the below diagram, each node x has at most 3 incoming arcs and has at most 3 outgoing arcs. Traversing each arc is $\Theta(1)$. So basically, if we start from a minimum node, and keep advancing to the successor nodes, we do essentially in-order traversal that is, however, iterative instead of recursive. Same argument for starting from the maximum node via get_predecessor.

Now, we do the same traversal but in "both directions" (the left_finger proceeds towards successor nodes and right_finger proceeds towards predecessor nodes, and we terminate (at latest) when the two fingers meet. Thus, running time is linear in tree size and space complexity constant since no recursion is involved.

In-order traversal and successor traversal

$\endgroup$
  • $\begingroup$ @coderodde, I have doubts that I hope you can help me with. First, this seems like it would rely on being able to access the node's parent, which you could argue is possible in a RB tree. Then you mention this works for any tree, but it seems impossible to work with a tree that has no node reference to it's parent. Without a reference to the parent we can't keep track of parents in constant space without modifying the tree. This means getSuccessor can make the total time at least $n \log n$. $\endgroup$ – ryan Jul 1 '17 at 17:30
  • $\begingroup$ @ryan "works for any tree" - I meant that the algorithm works for trees of any topology (not necessarily balanced trees). As far I understand, RB-tree has to fix itself by starting at a node and going upwards towards root, which -- ultimately -- requires a parent fields in each node. I am confident that you can solve the problem even on trees whose nodes has no parent field, but that might be less efficient than $\Theta(n)$. $\endgroup$ – coderodde Jul 1 '17 at 17:40
-1
$\begingroup$

First thing that popped into my mind, was using a hashmap (or just a key - storage) while iterating.

In the HashTable, I would store an addend for the sum, and while iterating I would look up if the value is in the list.

Addends[] //KeySet
for value in Values {
   if(Addends.contains(value) // Pair found
     return true
   Addends.add(Sum - value)
}
$\endgroup$
  • $\begingroup$ Good idea, but it is not $\Theta(n)$ but $\mathcal O(n^2)$. $\endgroup$ – Evil Jun 30 '17 at 18:50
  • $\begingroup$ It's not. I am iterating only once and the KeySet lookup requires only O(1) $\endgroup$ – codeMoh Jun 30 '17 at 18:54
  • 1
    $\begingroup$ This is expected lookup time, also the average case is constant, but the worst case for the hash lookup is $\mathcal O(n)$, so it is not tight bound. If the KeySet has a tree underneath then it is $\mathcal O(log n)$ per lookup. $\endgroup$ – Evil Jun 30 '17 at 18:57
  • 1
    $\begingroup$ HashTable doesn't provide constant lookup, besides with additional table the constant space requirement is not met. $\endgroup$ – Evil Jun 30 '17 at 22:39
  • 1
    $\begingroup$ Auxiliary space is $\mathcal O(R)$, but $R$ may be arbitrary large, orders of magnitude greater than $n$. I agree that your solution is nice but under different constraints than given. Both time and space exceeds constraints. $\endgroup$ – Evil Jul 1 '17 at 23:21

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.