CODEWITHSUNDEEP
algorithmbinary-tree
Shamim Hafiz - MSFT
Shamim Hafiz - MSFT

Reputation: 22104

Numbers in Binary Search Tree(BST) adding to a certain value

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.

Upvotes: 4

Views: 1102

Answers (3)

piccolbo
piccolbo

Reputation: 1315

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.

Upvotes: 2

jonderry
jonderry

Reputation: 23633

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;
  }
}

Upvotes: 4

ruslik
ruslik

Reputation: 14880

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

Upvotes: -1

Related Questions