Yahoo Interview Question
Country: United States
depth first traversal returning the running sum of the entire sub tree when done. then pass that when running to the right to be added.
In this case, when I head left, I pass what should be added to the current node since this everything to the left of the parent which is left of the child node as well.
int trav(node* n, int addMe)
{
if(n==NULL)
return 0; //just in case never known ;-)
int leftSum=0;
n->value+=addMe;
if(n->left)
{
leftSum+=trav(n->left,addMe);
}
leftSum+=n->value;
if(n->right)
{
leftSum+=trav(n->right,leftSum);
}
return leftSum;
}
void updateTree(node* root)
{
int trav(root, 0)
}
Implement a method to calculate the sum of left sub tree and right sub tree for each node
Assign the node-> data to the sum of left subtree and return the total sum to the caller
void ChangeTree(TreeNode* t)
{
Sum(t);
}
int Sum(TreeNode* t)
{
int leftSum = 0;
int rightSum=0;
if(t==null)
{
return 0;
}
if(t->Left != null)
{
leftSum = Sum(t->Left);
}
if(t->Right != null)
{
rightSum = Sum(t->Right);
}
t->data = leftSum;
return t->data + leftSum + rightSum;
}
This updates the left subtree with the sum of the left children as well. There is no distinction between left and right subtrees. I don't think this algorithm works.
private int addSumLeftBST (BNode root, int value) {
int leftSum = 0, rightSum = 0, sum = 0;
if (root == null)
return 0;
leftSum = addSumLeftBST(root.getLeft(), value);
if (root.getLeft() != null)
sum = leftSum + root.getData();
else
sum = leftSum + root.getData() + value;
root.setData(sum);
rightSum = addSumLeftBST(root.getRight(), sum);
if ((root.getLeft() == null) && (root.getRight() == null))
rightSum = root.getData() + leftSum + rightSum;
else
rightSum = leftSum + rightSum;
return (rightSum);
}
psuedocode:
int RIGHT_SIDE = 0;
int LEFT_SIDE = 1;
int ROOT = 2;
int left_sum(node, side) {
// Base case.
if(node == null) {
return 0;
}
// Calculate the sum on the left side and add it to this node's value.
node.val += left_sum(node.left, LEFT_SIDE);
// If this node is the right child of its parent, we need to add the value of its parent
// because it is on the left side of the child. The left-sum of each node is always
// finalized before invoking the function on the right side of the node so the parent
// value is always in the proper state.
if(side == RIGHT_SIDE) node.val += node.parent.val;
// Safely calculate the left-sum on the right side of the tree after the current node
// has been fully evaluated.
left_sum(node.right, RIGHT_SIDE);
// Return the newly calculated value in case this is a left child and the parent is
// listening for a result. The right side is always ignored
return node.val;
}
// Example invocation.
void main() {
tree example_tree = new tree();
left_sum(tree.root, ROOT);
}
void leftsum(node *node)
{
if (!node)
return 0;
node->data = node->data + leftsum(node->left);
return node->data + leftsum(node->right);
}
This will properly bubble up the sums of the left side to the subtree root, but when you head node->rigth, how does that sum then get propagated to the nodes to the right?
do you need the sum to be propagated to the right? I think sum should be propagated to the parent of the left node i.e. sum of both left and right subnodes.
eg:
before:
5
2 6
1 3
after:
11
3 6
1 3
As you can see the parent of 2 should get the entire sum of the left and right subnodes not 3 in the "before" bst.
Isn't similar to changing root value to all the nodes which are before (including that node) in in-order traversal.
Algo:
1) first visit left node
2) then sum = sum + root-->data
3) root-->datra = sum
4) Visit right node
void changeData(Node root, int sum)
{
changeData(root.left,sum);
sum = sum + root.data;
root.data = sum + root.data;
changeData(root.right,sum);
}
void leftSum(tnode *tree){
if(tree == NULL)
return;
int sum = 0;
leftSumUtil(tree->left,&sum);
tree->value = sum + tree->value;
leftSum(tree->left);
leftSum(tree->right);
}
void leftSumUtil(tnode *tree,int *sum){
if(tree!=NULL){
leftSumUtil(tree->left,sum);
*sum = *sum + tree->value;
leftSumUtil(tree->right,sum);
}
}
struct node{
int val;
struct node *left;
struct node *right;
};
typedef struct node Node;
int sumReplace(Node *root) {
if (root == NULL) return 0;
if (root->left != NULL)
root->val += sumReplace(root->left);
if (root->right != NULL)
root->right->val += root->val;
sumReplace(root->right);
return root->val;
}
Isn't this a modification of inorder traversal?
void inorder_modif( node * root, int * sum ){
if( root == NULL )
return;
//go to left
inorder_modif( root->left );
//do operation
if( *sum == 0 ){
*sum = root->data;
}
else{
*sum += root->data;
root->data = *sum;
}
//go to right
inorder_modif( root->right );
}
int helper(TreeNode *root) {
if (!root->left && !root->right)
return root->val;
int l_sum = 0;
int r_sum = 0;
if (root->left) {
l_sum = helper(root->left);
}
if (root->right) {
r_sum = helper(root->right);
}
root->val += l_sum;
return root->val + r_sum;
}
void transform(TreeNode *root) {
helper(root);
}
It can be done through inorder traversal. Check the left branch and update the value to the parent node( left branch sum + parent node). Python based solution.
class BTree:
def __init__(self, value):
self.left = None
self.right = None
self.key = value
# get leftsum
def leftSum(root):
if root == None:
return 0
root.key += leftSum(root.left)
return root.key + leftSum(root.right)
# Crate root Node
root = BTree(10)
root.left = BTree(5)
root.right = BTree(6)
root.left.left = BTree(3)
root.left.right = BTree(2)
root.left.right.left = BTree(1)
leftSum(root)
Do vertical sum of a tree and then add all the vertical sums whose nodes falls left side of the node .
- Anonymous August 07, 2014example 1
/ \ vertical sum = {4, 2 , 12, 4, 7, 2 }
2 3
/ \ / \ for node with value 3 : 4+2+12+3=21
4 5 6 7
/ \
1 2