1
\$\begingroup\$

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: (<node-value>(<left subtree>)(<right subtree>)). 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 < 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?

\$\endgroup\$
7
  • \$\begingroup\$ I think it doesn't get much better than this. The time complexity of your code is linear with regard to the length of the input string and also to the size of the tree. There's hardly a way to do it more efficiently. \$\endgroup\$ Commented Apr 22, 2017 at 19:50
  • \$\begingroup\$ Maybe this should be more of an edit to the question rather than a comment, but is there any way of using regex to jump to the next correct node value to avoid iterating over noise characters? I've been working on exercises to try to improve my parsing, because I'm still rather unfamiliar with a lot of the tricks. Or in this case, would that be slower anyway if it were possible? \$\endgroup\$ Commented Apr 22, 2017 at 20:09
  • 1
    \$\begingroup\$ A regex would also iterate over the characters, just probably more efficiently, so it probably wouldn't be slower. But maybe it would be, since it takes some time to parse and compile the regex, and then there's some overhead of interpreting the compiled regex code. The problem is that regex would not be able to do it. The language you're parsing is not regular, so it cannot be reliably processed using regular expressions. \$\endgroup\$ Commented Apr 22, 2017 at 20:13
  • \$\begingroup\$ You could do it using regex, but it wouldn't be nice. You would have to replace all parentheses at a lower level with nothing, and then extract the numbers you'd want to sum. And the replacement of all lower levels parentheses would require a costly regex with group matching at multiple levels. Doable, but expensive. \$\endgroup\$ Commented Apr 22, 2017 at 20:19
  • 1
    \$\begingroup\$ Java regex library... :) \$\endgroup\$ Commented Apr 22, 2017 at 20:25

1 Answer 1

Reset to default
2
\$\begingroup\$

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.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.