## Amazon Interview Question

SDE1s- -2of 2 votes
Find sum of n elements after kth smallest element in BST. Tree is very large, you are not allowed to traverse the tree.

**Country:**India

Seems weird. I would say convert to min-heap and while you are looking at each node calculate the sum of the tree. Then pop-off `k` elements from the min-heap and subtract from the sum. But there's an implicit tree traversal there.

I don't see how you can calculate the sum of tree whose nodes you can't look at? Seems like a problem with the question.

Traverse the tree in in-order and while you're at it, decrement and track K. When K hits zero then sum N nodes (decrement N for each addition after K hits zero) and then short circuit once N reaches zero. Here's the implementation with runtime O(n+k):

```
public static int findNSumAfterK(TreeNode treeNode, int k, int n) {
CounterHolder counterHolder = new CounterHolder(k, n);
findSum(treeNode, counterHolder);
return counterHolder.sum;
}
private static void findSum(TreeNode treeNode, CounterHolder counterHolder) {
if (treeNode == null || counterHolder.n <= 0) return;
findSum(treeNode.left, counterHolder);
track(treeNode.data, counterHolder);
findSum(treeNode.right, counterHolder);
}
private static void track(int data, CounterHolder counterHolder) {
if (counterHolder.k == 0) {
if (counterHolder.n > 0) {
counterHolder.sum += data;
}
counterHolder.n--;
} else {
counterHolder.k--;
}
}
static class CounterHolder {
int k, n, sum;
public CounterHolder(int k, int n) {
this.k = k;
this.n = n;
}
}
static class TreeNode {
final int data;
TreeNode left;
TreeNode right;
TreeNode(int data) {
this.data = data;
}
}
```

If I can traverse, I may leverage inorder

```
void inorder(Node* nd, int k, int n, int& i, int& sum) { // i&sum is initialized to 0
if (i<n && nd->left) inorder(nd->left, k, n, i);
if (i<n) i++;
if (i >=k) sum += nd->value;
if (i<n && nd->right) inorder(nd->right, k, n, i);
}
```

Not that hard. I guess interviewer meant to avoid this kind by "no traversal".

But if I'm not allowed for it ?

Quite naive solution only I can come up with.

```
extern BSTTree* root;
Node* min(Node* root) {
if (root !=nullptr) return min(root->left);
else return root;
}
Node* nextLarge(Node* n) {
if (n==nullptr) return n;
else if (n->right != nullptr) return min(n->right);
else {
while (n->parent!=nullptr && n->parent->right==n) {
n = n->parent;
}
return n->parent;
}
}
int getNSumAfterSmallestK(Node* root, int k, int n) {
Node* nd = min(root);
for (int i=0; i<k-1; i++) {
nd = nextLarge(nd); // ignore if n is null 'cause tree is large enough
}
int sum = 0;
for (int i=0; i<n; i++) {
nd = nextLarge(nd);
sum += nd->value;
}
return sum;
}
```

What does it mean "you are not allowed to traverse the tree"?

I assume it means you are not allowed to walk the tree node-by-node to get the k-th element or to calculate the sum (so no O(n) solution...)

1) how to find the kth element

if the tree is very large, finding the k-th element with in-order traversal is slow. It takes O(k). Faster is, if you store on each node the size of the subtree and modify the in-order traversal to skip whole subtrees if theire size is larger than k-remaining, this takes O(lg(n)), where n is the

number of nodes (it becomes a pre-order traversal, BST assumed to be balanced):

2) how to calculate the sum

Similar to 1) maintain the sum of the subtree, in addition of the tree-size, per nodes. Now the whole tree is the sum of all nodes. Everytime you skip a subtree, you remove that subtree's

sum from the current sum:

3) This requires two additional fields per Node, so space complexity is O(n). Time complexity

- ChrisK December 08, 2016is therefore O(lg(n)). In addition all tree operations must maintain this additional fields which has no impact on the big-O of the run-time of insert, delete, update of known self-balancing BSTs like RGB, AVL, 2-3 etc. Further it's worth mentioning it only makes sense if the tree is roughly balanced...