Amazon Interview Question
SDE1sCountry: United States
Interview Type: Phone Interview
Consider below BST :
12
/ \
10 24
/ / \
5 14 36
/ \ \
4 6 18
/ \
16 21
With above algo, can you give the answer it will give for nodes with values, 12, 14 and 6?
(In-order traversal is 4, 5, 6, 10, 12, 14, 16, 18, 21, 24, 36)
I also considered the reverse in-order traversal that geekvjaks mentioned. Here's my version:
void sumGreaterNodes(Node n, IntWrap sum) {
if (n.right != null)
sumGreaterNodes(n.right, sum);
n.greaterValuesSum = sum.value;
sum.value += n.value;
if (n.left != null)
sumGreaterNodes(n.left, sum);
}
class IntWrap {
public int value;
}
What is meant by "You have to compute for each node the summation of all nodes whose value is greater than the current node." ?
Do I have to find all nodes whose value is less than the sum of its children?
class Node:
def __init__(self, value):
self.left = None
self.right = None
self.val = value
class Tree:
def __init__(self):
self.root = None
def add(self, value):
node = Node(value)
if not self.root:
self.root = node
else:
current = self.root
while (True):
if current.val < node.val:
if not current.right:
current.right = node
break
current = current.right
else:
if not current.left:
current.left = node
break
current = current.left
def helperSum(self, current, value):
s = 0
if current:
if current.left and current.left.val > value:
s = s + self.helperSum(current.left, value)
if current.val > value:
s = s + current.val
if current.right:
s = s + self.helperSum(current.right, value)
return s
def getSum(self, value):
return self.helperSum(self.root, value)
vector<Node> traverse(Node *root, vector<Node> ls){
ls.push_back(*root);
if(root->left != NULL ){
ls = traverse(root->left,ls);
}
if(root->right != NULL ){
ls = traverse(root->right,ls);
}
return ls;
}
struct myclass {
bool operator() (const Node &i, const Node &j) { return (i.data < j.data);}
} myobject;
void getNodeSum(Node *root, vector<Node> ls){
ls = traverse(root,ls);
// sort ls in ascending order
sort(ls.begin(),ls.end(),myobject);
int s = 0;
for(int k = ls.size()-1; k >= 0 ; k--){
s += ls[k].data;
ls[k].sum = s;
}
for(vector<Node>::iterator it = ls.begin(); it != ls.end(); ++it){
Node n = (Node)*it;
cout<<"Node "<<n.data<<" has sum = "<<n.sum<<endl;
}
}
Reverse inorder traversal. right->root->left. Calculate the sum and pass to left node.
- geekyjaks May 16, 2014