## Amazon Interview Question

Interns**Country:**India

**Interview Type:**Phone Interview

Can you please explain me about your algo. I am bit confused. Just tell me with small example.

Thank you.

1.see I m traversing right subtree first so we will get traversal in decreasing order.

2.And counter sum will held the sum of traverse elements

like if 5,3,2 is traversed thn sum will have 10.

3. for the current node we will change its value with the sum.

4. and current elements value before updation we will add in sum also bcz we need it further.

@Nuruddin-

See I m thinking of this problem as the largest node will have zero in updated tree since there is no larger node thn it. SO I m updating it with zero thats why I performed subtraction.

If u want that largest node will contain the vlue of its own in updated tree is well then no need of subtraction.

Let me know if u have any more issues

1) Each node will receive some values from left subtree and from right subtree.

2) That node will change its value with : selfvalue + sum of value received from right subtree

3) That node will return new pair of values to its parent: < sum of left subtree value, node's new value >

I can explain algo with an example:

```
left assume following BST:
41
40 50
39 45 55
node 40 will return <39, 40>
node 50 will return <45, (50+55)> -- <45, 105>
node 41 will receive left pair<39, 40> and right pair <45, 105>
node 41 will change -- 41 + right pair --> 41 + 45 + 105 -->191
node 41 will return <sumofleftpairvalue + newsumeofcurrentnode> -- <(39+40), 192> -- <79,192>
this will continue
```

sudo code:

```
pair<int, int> updateBst (tree *root)
{
if (!root) return <0,0>
if (leafnode) return <0, root->key>
leftpair = updateBst (root->left)
rightpair = updateBst (root->right)
root->key += rightpair.first + rightpair.second;
return < (leftpair.first+leftpair.second) , root->key>
}
```

Reverse Inorder traversal which lists the nodes in descending followed by sum at each node works perfectly well

```
int sum=0;
void descending(myBSTNode focusNode) {
if (focusNode != null) {
descending(focusNode.rightChild);
sum+=focusNode.key;
focusNode.key=sum-focusNode.key;
System.out.println(focusNode.name + " has a key " + focusNode.key);
descending(focusNode.leftChild);
}
}
```

Output of Reverse Inorder traversal:

Salesman has a key 85

Sales manager has a key 75

Boss has a key 50

Secretary has a key 30

VP has a key 25

Office manager has a key 15

Final Output

Salesman has a key 0

Sales manager has a key 85

Boss has a key 160

Secretary has a key 210

VP has a key 240

Office manager has a key 265

```
public class ReplaceBST {
private static List<Integer> list = new LinkedList<Integer>();
private static List<Node> nodeList = new LinkedList<Node>();
public static void replace(Node root) {
if(root == null) return;
replace(root.left);
list.add(root.value);
nodeList.add(root);
replace(root.right);
}
public static void inOrderTreeWalk(Node root) {
if(root == null) return;
inOrderTreeWalk(root.left);
System.out.println(root.value);
inOrderTreeWalk(root.right);
}
public static void main(String[] args) {
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
Node node6 = new Node(6);
Node node7 = new Node(7);
node4.left = node2;
node2.left = node1;
node1.right = node3;
node4.right = node6;
node6.left = node5;
node6.right = node7;
replace(node4);
int cumul = 0;
for(int i = list.size() - 1;i >= 0;i--) {
nodeList.get(i).value = cumul;
cumul += list.get(i);
}
inOrderTreeWalk(node4);
}
}
```

1. apply reverse inorder

2. keep track of sum of nodes while traversing

3. change the value of roots while traversing

-->sum is a static variable

- saumya.tyagi6 January 21, 2014