Sum of nodes at a given depth of a binary tree (String representation) Given a binary tree of integers and a depth, the goal is to find the sum of all node values at the depth in the tree. The root is considered depth 0, and the tree is given as a string in the format: (&lt;node-value&gt;(&lt;left subtree&gt;)(&lt;right subtree&gt;)). For example, treeLevelSum("(5(42)(-37(28)()))", 1) should return 5.

int treeLevelSum(String tree, int k) {
    int sum   = 0;

    int depth = 0;
    int value = 0;
    int sign  = 1;
    for (int i = 1; i &lt; tree.length(); i++) {
        if (tree.charAt(i) == '(') {
            depth += 1;
        } else if (tree.charAt(i) == ')') {
            sum   += value * sign;
            value  = 0;
            sign   = 1;
            depth -= 1;
        } else if (depth == k) {
            if (tree.charAt(i) == '-') {
                sign = -1;
            } else {
                value = value * 10 + (tree.charAt(i) - '0');
            }
        }
    }

    return sum;
}


I was just wondering if there was a better way of parsing this, or if there was any way of improving efficiency? Is there a known "best solution" for this kind of problem?
Most likely you can't improve too much on this approach, as you do need to scan the entire string, and you don't convert any unneeded values. So as I see it there are three things you could try changing, but most likely they either not make a difference, or possibly even increase running time.


Pre-calculate the length of the string – Not quite sure how Java handles this one, but in the end-condition of your for loop you do tree.length(). If this had been a costly function, then some languages would execute this function for each run through the loop, and would benefit from this being done in front of the for loop. The length of your string isn't going to change in this case, so it should be safe to just do it once before the loop.
Not using repeated calls to tree.charAt(i) – In your code, in the worst case, you call tree.charAt(i) 4 times (when calculating the value). This could possibly be done outside the if block just once. However, this function is \$O(1)\$, so the benefit wouldn't be large. 
Change the value extraction – Another change which could be made, is to change the way you extract the value. An alternative approach could be that after detecting the opening paranthesis, you could scan the string for the entire value string, and then convert it.

This could be done by preserving the start index of the value string, search until you hit a new parenthesis, and then convert the substring directly into a number. However, this doesn't need to be a faster method.


I've given no code in this answer, but I think you're getting the ideas. 

One comment though on chosen algorithm, is that you calculate the value when on the correct depth, but you don't actually use it before you've traversed all child trees and then hit the end parenthesis.This isn't a problem in the current specification, but if it changed to sum up all values on multiple depths, it would fail miserably.

My final comment, is that your code does look clean and tidy with good names. If I'd change anything I would possibly add a little more vertical space, and some comments as to what the method is doing.