Binary Tree Level Sum -

Question

A basic Java sample: Given a binary tree and an integer which is the depth of the target level. And calculate the sum of the nodes in the target level.

I am adding the value in the functions to the left and right node. Why this solution doesn't work in this case, Can anyone help explain?

Also, when the travese function got returned, is it returning to the parent root or more like break; in for loop and the flow got stopped?

private int sum;

public int levelSum(TreeNode root, int level) {
    sum = 0;
    traverse(root, 1, level, 0);
    return sum;
}

public void traverse(TreeNode root, int depth, int level, int sum) {
    if(root == null) {
        return;
    }

    if(depth == level) {
        return;
    }

    if(root.left != null) {
        traverse(root.left, depth + 1, level, sum + root.left.val);
    }

    if(root.right != null) {
        traverse(root.right, depth + 1, level, sum + root.right.val);
    }
}

Except for the initialization, you never assign to sum in the levelSum routine. And traverse returns void, so you have no way to pass the intermediate sum values back up the call stack. You should probably merge these two routines into a single function that returns int. — Jim Lewis
I see no for loop in your posted code, so I cannot answer your last question. — MikeCAT

MikeCAT MikeCAT · Accepted Answer · 2016-05-12T00:47:36

First of all, you didn't return the result of summation. You will have to return it.

Then, since you wrote "in the target level", I guess you will have to sum up nodes only in the target level, not nodes before the level.

Try this:

public int levelSum(TreeNode root, int level) {
    return traverse(root, 1, level);

}

public void traverse(TreeNode root, int depth, int level){
    int sum = 0;

    if(root == null || depth > level){
        return 0;
    }

    if (depth == level) sum += root.val;

    if(root.left != null) {
        sum += traverse(root.left, depth + 1, level);
    }

    if(root.right != null) {
        sum += traverse(root.right, depth + 1, level);
    }

    return sum;
}

Binary Tree Level Sum -

1 Answers