CareerCup

The problem itself is tricky, it says constant space but doesn't require it to be storage efficient.

The solution is:

int maxValue = tree.getMaxValue() // by keeping visiting right most branch

int[] array = new int[maxValue] // not storage efficient
for each node value in the tree, set array[value] = 1 // O(n)

for each node value in the tree, check whether array[K-value] exists. If exists, print the pair. // O(n)

Thus the solution is O(n) and the storage is a constant value depending the largest node value.

1) convert the given BST into an sorted array A with in-order traverse,
2) two index (i=0, j=arraysize-1)
3) loop over:
3.a) if A[i]+A[j]>k => j--;
3.b) if A[i]+A[j]<k => i++;
3.c) output (i,j)

ok, if we can modify the input BST, we can first convert it into a double linked list, and do the same. the time complexity will be O(n), and space O(1)

I would say this cannot be done in O(n). It is necessary that we examine each element and look for existence of its pairs that sums to k. It would take O(n) just to go through each element. In my view, the best possible is O(nlog n)

delete not good.

Why do we need a sorted array in this case?

left = findSmallestValue(); // O(logN)
right = findLargestValue(); // O(logN)
while (left <= right) {
	if (left + right == k) output(left,right); // if there are duplicates, need to handle all pairs
	else if (left + right < k) left = successor(left);
	else right = predecessor(right);
}

This algorithm practically runs in-order traversal twice. O(n)

In-order traversal of BST sorts data in ascending order
as A B C D E F G if you
1. Traverse the left subtree.
2. Visit the root.
3. Traverse the right subtree.


and you can sort it in deciding order
G F E D C B A if you
1. Traverse the right subtree.
2. Visit the root.
3. Traverse the left subtree.

it can be done without recursion
so you can imagine we've got a sorted array A B C D E F G and we have pointers/reference at head and tail, and we can use them to traverse across 'virtual' array to find pair of nodes whose sum is equal to a given number k

time complexity is O(n) and space complexity is O(1)

Improving on zouzhile's idea,
1 we can create an array A of size k
2. Initialise the array with null
2. Do an inorder traversal of the tree (O(n))till a node with value k or greater than k arrives. And setting the array A[node.value] = 1 (or a pointer to the node using perhaps a hashmap)
3. Traverse the array and for each A[i]!=null, find if A[k-i] is null. If not null then, then we have a pair and from this pair of indices of A, we can get the nodes.
Runtime is O(n) and space is constant with respect to k.