iLabs Interview Question Tech Leads
Country: India
Interview Type: In-Person
Good one. Another alternative with similar effect is to create a 'reflected' BST where min node will occur at the place of max node etc. Then do an inorder traversal, keeping the running cumulative sum and updating the node values and then 'reflect' the BST back.
Doing a reverse inorder is more efficient both in terms of time and space though.
public int replaceNodeWithRightSubtree(Node node){
if(node==null)return 0;
int rightSum=0;
if(node.right!=null){
rightSum=replaceNodeWithRightSubtree(node.right);
}
node.value=node.value+rightSum;
if(node.left!=null){
node.left.value=node.left.value+node.value;
replaceNodeWithRightSubtree(node.left);
}
return node.value;
}
You posting question and answer so other can verify your sol?
You have no friends to bounce the solution onto so you are a loner.
- Guest _BS_
Do a reverse inorder keeping a cumulative sum of the elements seen so far.
- Subbu. November 24, 2013void ReplaceGreaterSum(Tree *node, long *sum) { if (node == NULL) return; if (node->Right) ReplaceGreaterSum(node->Right, sum); *sum = *sum + node->Value; node->Value = *sum; if (node->Left) ReplaceGreateSum(node->Left, sum); } void ReplaceGreaterSum(Tree *root) { long sum = 0; ReplaceGreaterSum(root, &sum); }