Yahoo Interview Question


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

- Anonymous August 07, 2014 | Flag Reply
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

- Anonymous August 07, 2014 | Flag Reply
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)
}

- Anonymous August 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

have you tested your code with some inputs?

- aka[1] August 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous August 11, 2014 | Flag
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.

- aka[1] August 11, 2014 | Flag
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;

- Anonymous August 08, 2014 | Flag Reply
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;
}

- PartTimer August 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

t->data += leftSum;

- gdg August 08, 2014 | Flag
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.

- Anonymous August 08, 2014 | Flag
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

- AK August 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

What happens to the leaf node?

- kr.neerav August 08, 2014 | Flag Reply
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

- Anonymous August 08, 2014 | Flag Reply
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);
	}

- Anonymous August 09, 2014 | Flag Reply
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);
}

- enzeart August 09, 2014 | Flag Reply
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);
}

- aka[1] August 10, 2014 | Flag Reply
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?

- Anonymous August 11, 2014 | Flag
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.

- aka[1] August 11, 2014 | Flag
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);
	}

- aviundefined August 13, 2014 | Flag Reply
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

- Kangsan August 28, 2014 | Flag
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);
}
}

- Shobhank October 13, 2014 | Flag Reply
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;
}

- Kamaldeep Singh October 22, 2014 | Flag Reply
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 );
}

- nharryp December 08, 2014 | Flag Reply
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.

- nharryp January 27, 2015 | Flag
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);
}

- shawn February 05, 2016 | Flag Reply
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);
        }

}

- Spectral July 18, 2016 | Flag Reply
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);
        }

}

- Spectral July 18, 2016 | Flag Reply
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)

- som March 14, 2017 | Flag Reply


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