Digits in the binary search tree (BST), adding to a specific value

Question

Given BST, you can find two numbers that add up to a given value, in O (n) time and a little extra memory. A little extra memory implies that you cannot copy the entire BST to an array.

Answer 1

This can be done in O (n) time and O (1) extra memory if you have both child and parent pointers. You save two pointers, x and y, and start x with the minimum element and y at the maximum. If the sum of these two elements is too low, you move x to your successor, and if it is too high, you move y to your predecessor. You may report an error if x points to a larger element than y. Each edge in the tree goes no more than two times for a common O (n) workaround, and your only memory usage is two pointers. Without parent pointers, you need to remember the sequence of ancestors for 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 (similar code for the 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; } } 

Answer 2

I think jonderry is very close, but parent pointers require \ Omega (n) memory, that is, they significantly affect memory usage. What he does is two coordinated transitions in opposite directions (from small to large and viveversa), which try to keep the amount always close to the target, and you can handle these two stacks, and the stacks can only grow to the depth of the tree and this is O (log n). I do not know if there is this “small” additional memory, but, of course, it is less than additional memory and o (n). Thus, this is exactly the same as in jonderry's own comment, but there is no penalty for execution, because moving the binary tree using only the stack is a well-known and efficient and definitely O (n) operation. Thus, you increase the iterator ii and decrease the 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 ran into the same problem in the context of calculating pseudo-media, the median of all pairwise averages in the sample.

Answer 3

Yes, if you parse it, as it will be a sorted array.