Given a BST, is it possible to find two numbers that add up to a given value, in O(n) time and little additional memory. By little additional memory, it is implied that you can't copy the entire BST into an array.
But that would mean you would need additional memory which is equal to the number of elements in the BST. The original post strictly wants to prevent this.
Gunner
2010-10-13 19:14:53
@Gunner have you ever heard such words as `inorder`, `preorder` or `postorer`?
ruslik
2010-10-13 19:40:14
@ruslik: Yes I am aware of the words, but would it be possible to perform two different parsing and combine the two conveniently to obtain the desired answer.
Gunner
2010-10-14 08:28:13
+3
A:
This can be accomplished in O(n) time and O(1) additional memory if you have both child and parent pointers. You keep two pointers, x and y, and start x at the minimum element and y at the maximum. If the sum of these two elements is too low, you move x to its successor, and if it's too high you move y to its predecessor. You can report a failure once x points to a larger element than y. Each edge in the tree is traversed at most twice for a total of O(n) edge traversals, and your only memory usage is the two pointers. Without parent pointers, you need to remember the sequence of ancestors to the root, which is at least Omega(log n) and possibly higher if the tree is unbalanced.
To find a successor, you can use the following pseudocode (analogous code for predecessor):
succ(x) {
if (x.right != null) {
ret = x.right;
while (ret.left != null) ret = ret.left;
return ret;
} else {
retc = x;
while (retc.parent != null && retc.parent < x) retc = retc.parent;
if (retc.parent != null && retc.parent > x) return retc.parent;
else return null;
}
}
jonderry
2010-10-13 18:02:40
This sounds more like it. Having references to parents would certainly help to achieve. Perhaps this would be the final acceptable answer, but I am waiting to see if someone can suggest one without needing parents and not requiring to store the ancestor tree.
Gunner
2010-10-13 19:12:09
@jonderry: Could you please edit your answer to add the code for the methods, GetSuccessor(x) and GetPredecessor(y)? Thanks.
Gunner
2010-10-13 19:13:46
@Gunner, isn't this almost exactly what I said (only moving in from the outside)? The main addition is pointing out the necessity of parent pointers, which I assumed because STL containers have them.
JoshD
2010-10-13 19:18:01
@Gunner, you need to keep parent pointers because otherwise you don't know how to get back up the tree when you've traversed to a deep level in the tree. You could avoid this by only remembering some parents, and traversing more edges, but you pay a large penalty in running time.
jonderry
2010-10-13 19:58:17
@jonderry: Thanks for the edit. I think it maybe possible to combine the two else ifs into a single block, since in either case you are comparing the value of x with one of it's ancestors.
Gunner
2010-10-14 08:25:41
`succ(x)` and the comparable `prev(x)` are amortized `O(ln(N))` if balanced; so the overall running time is actually `O(N ln(N))`.
Eamon Nerbonne
2010-10-14 23:54:05
+1
A:
I think jonderry is very close, but the parent pointers require \Omega(n) memory, that is they add substantially to memory usage. What he is doing is two coordinated traversals in opposite directions (small to large and viveversa) trying to keep the sum always close to the target and you can manage that with two stacks, and the stacks can only grow up to the depth of the tree and that is O(log n). I don't know if that's "little" additional memory, but certainly it is less additional memory and o(n). So this is exactly as in jonderry own comment, but there is no runtime penalty because traversing a binary tree using only a stack is a well known and efficient and definitely O(n) operation. So you have increasing iterator ii and a decreasing iterator di.
x = ii.next()
y = di.next()
while (true) {
try:
if x + y > target {y = di.next()}
if x + y < target {x = ii.next()}
if x + y == target {return (x,y)}
except IterError:
break
}
return None
I had just run into the same problem in the context of computing the pseudomedian, the median of all pairwise averages in a sample.
piccolbo
2010-10-14 23:45:17
So to implement ii.next() and di.next(),you would need to maintain stack right?
Gunner
2010-10-15 05:17:23
I guess there has to be a compromise between your and jonderry's method. If references to parents exist, we can always do the task with constant additional memory. Your method would be the best if no references to parent's exist. Also, the additional memory used is also minimal by your method.
Gunner
2010-10-15 05:24:45
Hey it just occurred to me, if you have to search up the stack, then why not search down the tree in the first place. That is the O(nlog(n)). If you need to keep on reaching to parent nodes, it would be same as going down from the root in the first place. This applies to jonderry's solution also.
Gunner
2010-10-15 05:28:17
Gunner-3 unclear, but it's a traversal, why are we still discussing it? There is nothing to discover about it.
piccolbo
2010-10-15 07:22:43
A:
Looks like it isn't actually possible to do this in O(n) time, since most of the solutions mentioned above would implicitly perform some kind of log(n) search at each stage.
A possible way would be to convert the BST to a list. I read somewhere that it can be done in O(n) time. And after that, it's also O(n) time searching.
Of course this would mean, we would have lost our original BST, but for the sake of this problem, it would not matter.
Gunner
2010-10-17 08:55:39