Amazon Interview Question
SDE-2sTeam: Kindle
Country: India
Interview Type: Written Test
public void replaceNodeBySumOfGreaterChildren(TreeNode root) {
// Do PreOrder traversal and invoke tree-sum for each node.
// Order is import so that updated value of a node, does not affect values of other nodes.
// So we can use only In order or PreOrder, but not PostOrder
if (root == null)
return;
root.data = getTreeSum(root.rChild);
replaceNodeBySumOfGreaterChildren(root.lChild);
replaceNodeBySumOfGreaterChildren(root.rChild);
}
public int getTreeSum(TreeNode root) {
if (root == null)
return 0;
return root.data + getTreeSum(root.lChild) + getTreeSum(root.rChild);
}
Am I missing something in question?
As per my understanding a BST is given and a particular node (whose value is k, say) is given. Now firstly we have to find sum of all nodes whose value is greater than k. Once we have the sum, now each node value of BST should be replaced with 'root->data+sum'.
If that is the problem, then none of the above solutions listed above are helpful?
I must be missing something grave.
public class Data{
int sumSoFar;
public Data(int s){
sumSoFar = s;
}
}
class Node{
int value;
Node left;
Node right;
}
public Node updateSum(Node n){
updateHelp(n,new Data(0));
}
private void updateHelp(Node n, Data d){
if(n == null){
return;
}
updateHelp(n.right,d);
n.val += d.sumSoFar;
d.sumSoFar = val;
updateHelp(n.left, d);
}
Visit each node and replace its value with the sum of node values to the right of it.
public class Solution {
public void replaceInPlaceWithValuesGreaterThanSelf(TreeNode root){
if(root == null)
return;
replaceWithSumOfNodesGreaterThanitself(root.left);
replaceWithSumOfNodesGreaterThanitself(root);
replaceWithSumOfNodesGreaterThanitself(root.right);
}
private TreeNode replaceWithSumOfNodesGreaterThanitself(TreeNode root){
if(root.right==null)
return root;
root.data=sumOfChilds(root.right);
return root;
}
private int sumOfChilds(TreeNode root){
if(root == null)
return 0;
return root.data+sumOfChilds(root.left)+sumOfChilds(root.right);
}
}
class TreeNode{
int data;
TreeNode left;
TreeNode right;
public TreeNode(int data){
this.data = data;
this.left = null;
this.right =null;
}
}
class Node:
def __init__(self, val):
self.left = None
self.right = None
self.val = val
def replace_with_greater(root, sum_val):
if not root:
return sum_val
val = root.val
sum_val = replace_with_greater(root.right, sum_val)
root.val = max(root.val, sum_val)
sum_val += val
sum_val = replace_with_greater(root.left, sum_val)
return sum_val
Here's a recursive solution. The idea is that for each Node n, we can set that Nodes value as the sum of nodes larger than it that come before it in a preorder traversal plus the sum of the right subtree of that node, plus its value. Hence we can have our function's return value yield subtree sizes, and use a parameter sum_above to pass in the sum we've seen so far larger than the current value. Thus we can compute the solution recursively in linear time and constant space:
int replaceNodes(TreeNode*& root, int sum_above) {
if (root == 0) {
return 0;
}
int sum_right = replaceNodes(root->right, sum_above);
int sum_left = replaceNodes(root->left, sum_right + sum_above + root->data);
int temp = root->data;
root->data = sum_right + sum_above + temp;
return sum_right + sum_left + temp;
}
Start from the right most node, that will remain as is, since it is the largest node. Then as you move back up, add the sum from the right side to the value, and send the sum to the left (since all the values on the left will be less than all on right).
void updateWithSum(Node root) {
updateWithSum(root, 0);
}
int updateWithSum(Node root, int sumSoFar) {
if (root == null) {
return sumSoFar;
}
root.value += updateWithSum(root.right, sumSoFar);
int sumFromLeft = updateWithSum(root.left, root.Value);
return sumFromLeft;
}
Its a simple solution.
Do reverse inorder iteration and keep a track of sum. For every node add the value of the sum so far.
public void reverseInOrder(TreeNode root, int sum) {
if (root == null) {
return;
}
reverseInOrder(root.right, sum);
sum += root.val;
root.val = sum;
reverseInOrder(root.left, sum);
}
Do they ask such easy questions for SDE-2?
- elkon March 12, 2017