## Amazon Interview Question

SDE1s**Country:**India

traverse the given tree with maps which contain pairs of node's value and sum.

in the example shown, while traversing the node '80', the traversing method is given a map which has entries with keys 60, 50. it sums values less than 60 or 50 among the children below the node (by recursion), and update the sums to the map.

the computation complexity is O(n) and storage complexity is O(logn).

At every node, will it be required to iterate over the entries in the map and add to sum if the condition is met? If so, time complexity will be be n * log n

The actual run time depends upon the type of tree. If it is skew tree, then it will be O(n2), otherwise if it is balanced tree, then O(nlgn).

```
#include <iostream>
#include <unordered_map>
using namespace std;
struct tree{
int data;
struct tree *left,*right;
tree(int data) {
this->data = data;
left = right = NULL;
}
};
void find(tree *root,unordered_map<tree *,pair<int,int> > &m)
{
if(!root) return;
for(auto i : m)
if(root->data < i.second.first)
m[i.first].second += root->data;
m[root] = make_pair(root->data,0);
find(root->left,m);
find(root->right,m);
cout<<m[root].second<<" ";
}
int main()
{
tree *root = new tree(6);
root->left = new tree(3);
root->right = new tree(5);
root->right->left = new tree(18);
root->right->right = new tree(5);
root->left->left = new tree(4);
root->left->right = new tree(2);
unordered_map<tree *,pair<int,int> > m;
find(root,m);
return 0;
}
```

Can be done in n log n if tree is balanced.

Algo:

1. Conduct a depth first traversal

2. At each stage, maintain a list of ancestors (size log n if balanced)

3. For each ancestor, add to sum if condition is met

4. Add self to list of ancestors and traverse children

5. Get the sum calculated during the traversal of the children

- Ankit Sinha February 16, 2015