## Yahoo Interview Question

• 1
of 1 vote

Country: United States

Comment hidden because of low score. Click to expand.
1
of 1 vote

Do vertical sum of a tree and then add all the vertical sums whose nodes falls left side of the node .

example 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

Comment hidden because of low score. Click to expand.
0
of 0 vote

Do vertical sum of a tree and then add all the vertical sums whose nodes falls left side of the node .

example 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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)
}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

have you tested your code with some inputs?

Comment hidden because of low score. Click to expand.
0
of 0 votes

nope, but you are more than welcome to try it out

Comment hidden because of low score. Click to expand.
0
of 0 votes

It doesn't work with any inputs. Please check for sanity cases at least before posting your code. Good thing is that you have tried to explain your logic which is better than just dumping code.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Init sum as zero,
then do in-order traversal,
foreach node,
sum += node.value;
node.value = sum;

Comment hidden because of low score. Click to expand.
0
of 4 vote

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;
}

Comment hidden because of low score. Click to expand.
0
of 0 votes

``t->data += leftSum;``

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 votes

doesn't work. Try for below BST input:
6,5,4,3,7 ---6 is root

Comment hidden because of low score. Click to expand.
0
of 0 vote

What happens to the leaf node?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def sum_values(node, total=0):
if node is None:
return 0

sum_left = sum_values(node.left)
old_value = node.value
node.value = sum_left + node.value + total
sum_right = sum_values(node.right, node.value)
return old_value + sum_left + sum_right``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void leftsum(node *node)
{
if (!node)
return 0;
node->data = node->data + leftsum(node->left);
return node->data + leftsum(node->right);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

Comment hidden because of low score. Click to expand.
0
of 0 votes

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.``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

unless the variable sum is a global, it wouldn't reflect the left child tree's sum on the current node

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 );
}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

while checking if *sum=0 which has been done to check if it is the left-most leaf node, do it by passing a variable/flag (since *sum can be 0 if nodes are allowed negative values). Also pass sum each time or make it global.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void sumOfLeftNodes(Node root) {
if (root == null) return;
sumOfLeftNodes(root.getLeft());
sumOfLeftNodes(root.getRight());
if (root.getLeft() != null) {
int sum = root.getData() + root.getLeft().getData();
root.setData(sum);
}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void sumOfLeftNodes(Node root) {
if (root == null) return;
sumOfLeftNodes(root.getLeft());
sumOfLeftNodes(root.getRight());
if (root.getLeft() != null) {
int sum = root.getData() + root.getLeft().getData();
root.setData(sum);
}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)``````

Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More