Calculate the sum at a level of a binary tree represented in a String Fair preface: This is an interview question I would like to improve my knowledge of. I got some rest, and re-solved the problem with a fresh/unpanicked mind.


Given input of the type (10(5(3)(12))(14(11)(17)))
which would represent the following tree

 n=0            10
 n=1       5         14
 n=2    3    12    11   17 


My task is to find the summation of values at a particular tier, like \$5+14=19\$ which is the sum for \$n=1\$, or \$3+12+11+17=43\$ the sum for \$n=2\$.

Considering this is a binary tree, a recursive function seems appropriate.

My main utility functions are:


stripFirstLastParen – strips the first and last paren
getCurrentVal – retrieves the value of the current node
getChildren – retrieves the left and right nodes




var input = 
"(10(5(3)(12))(14(11)(17)))";

function stripFirstLastParen(input){
  if(input[0] !== "(" || input[input.length - 1] !== ")"){
    console.error("unbalanced parens")
  }
  else{
    input = input.substr(1);
    input = input.substring(0, input.length - 1);
  }
  return input;
}

function getCurrentVal(input){
  var val = "";
  while(input[0] !== "(" &amp;&amp; input[0] !== ")" &amp;&amp; input.length){
    val += input[0];
    input = input.substr(1);
  }
  return {
    val,
    input
  }
}

function getChildren(input){
  var val = "";
  if(input.length == 0){
    return {
      left: "",
      right: ""
    }
  }
  if(input[0] !== "("){
    console.error("no open paren at start");
  }
  val += input[0];
  input = input.substr(1);
  var parenStack = 1;
  while(parenStack &gt; 0){
    if(input[0] == ")"){
      parenStack--;
    }
    else if(input[0] == "("){
      parenStack++;
    }
    val += input[0];
    input = input.substr(1);
  }
  return {
    left: val, 
    right: input
  }
}

function getValueForLevel(input, k){
  var totalValue = 0;
  input = stripFirstLastParen(input);
  var currentValue = getCurrentVal(input);
  var children = getChildren(currentValue.input);
  if(k &gt; 0){ 
    if(children.left.length){
      totalValue += getValueForLevel(children.left, k-1);
    }
    if(children.right.length){
      totalValue += getValueForLevel(children.right, k-1);
    }
  }
  else if(k == 0){
    totalValue += JSON.parse(currentValue.val);
  }
  return totalValue;
}

var test = getValueForLevel(input, 2);
console.log(test);




My main concerns are:


String manipulation. How should I properly be passing the altered string throughout the recursive function? Callout for lines like

  var currentValue = getCurrentVal(input);
  var children = getChildren(currentValue.input);



Where the getChildren function relies on getCurrentVal removing the value from the string itself, that feels dirty. 


Complexity. I'm having difficulty describing the complexity of my procedure, and would argue that it's somewhere between \$O(n)\$ and \$O(n^2)\$, so is it \$O(n^2)\$? Considering the parens and values are removed as they are parsed, that lends itself to \$O(n)\$, but I feel it's \$O(n^2)\$ because of the duplicate parsing in order to create the child nodes. Is that correct? Can it be improved? 


I tried to keep the "spirit of the challenge" and re-completed this within the amount of time previously allotted (somewhere around 30-45 minutes). Suggestions and improvements need not consider this time restriction, but providing context is important.
Recursion:


  Considering this is a binary tree, a recursive function seems
  appropriate.


Recursion would be a natural choice if your input were a root tree node with tree nodes as children - a recursive data structure. However, your input is a 'flat' string representation of a tree. A simple iteration might actually be much easier to implement, read and execute.

Passing inputs:


  How should I properly be passing the altered string throughout the
  recursive function?


I think the recursive passing down of substrings representing nodes or node lists (children) is already pretty well done.

However, I would like to suggest a few improvements regarding the parsing functions and their return values:

Style:

Consider the getCurrentVal(input) function:

function getCurrentVal(input){
  var val = "";
  while(input[0] !== "(" &amp;&amp; input[0] !== ")" &amp;&amp; input.length){
    val += input[0];
    input = input.substr(1);
  }
  return {
    val,
    input
  }
}


The code is not very descriptive: It is not immediately obvious what this function does. 


The function name getCurrentVal is misleading, as you don't just return the node value, but also the children. 
The argument name input is meaningless, as all arguments are inputs.
The variable names are misleading, as you reuse input to store part of your output.


How about this alternative:

// Split node 'a(b)(c)' into value 'a' and children '(b)(c)':
function parseNode(node) {
  let split = Math.min(node.indexOf('('), node.indexOf(')'));
  if (split &lt; 0) split = node.length;
  return {
    value: node.slice(0, split),
    children: node.slice(split)
  };
}



'Parse' hints at the input being text or some other raw content.
'Node' carries more semantics than 'input'
Math.min and String.indexOf are more descriptive than a while loop.


Destructuring the resulting object improves readability:

var {value, children} = parseNode(node);


Also, when parsing integers, you shouldn't use JSON.parse(string) but the more specialized Number.parseInt(string) or the idiomatic type conversion via +string.

Further naming suggestions:


getValueForLevel -> getSumForLevel or sumTreeLevel
Consistency: Choose either val or value when naming currentValue.val, getCurrentVal, getValueForLevel


Complexity:


  Considering the parens and values are removed as they are parsed, that
  lends itself to O(n), but I feel it's O(n^2) because of the duplicate
  parsing in order to create the child nodes. Is that correct? Can it be
  improved?


First of all, let's define n as the length of the input string.
Then, let's look at the complexity of the helper functions:


stripFirstLastParen: O(n) because of input = input.substr(1)
getCurrentVal: O(n²) for worst-case input "1(2)(3)", "11(22)(33)", "111(222)(333)" and so on because of input = input.substr(1) within while (input.length). Yes, we break the loop as soon as we encounter the first parenthesis, but this doesn't happen before parsing roughly 1/3 * n characters for above input. The best-case complexity is however O(n) when the value has constant length.
getChildren has worst and best-case time complexity of O(n²) due to input = input.substr(1) within a while loop over input.


Now, we can tackle the complexity of getValueForLevel:


The first four lines are dominated by getChildren(currentValue.input). If the length of currentValue.input - the length of the children - is proportional to n, then it has a runtime complexity of O(n ²).
Then it calls getValueForLevel(children.left, k-1). It is easy to construct inputs which maximize the length of children.left such as "4(3(2(1))))" without right children. For this input, in each iteration, the length of children.left is reduced by 3.
The final call to JSON.parse is in O(n).


Adding the complexities together gives us: 

n² + (n-3)² + (n-6)² + ... + (n-3k)²


Thus, for k = 0 the runtime complexity is in O(n²) and for maximum k we have a runtime complexity of O(n³):



In general, the runtime complexity is bounded by O(kn²).

Alternative approach:

Following my introductory remarks about a possibly simpler iterative solution, here a possible implementation with linear runtime complexity:



// Sum integer tree nodes at given level: 
function sumTreeLevel(tree, level) {
  let tokens = tree.match(/(\(|[0-9]+|\))/g);
  let sum = 0;
  for (let token of tokens) {
    if (token === '(') {
      level--;
    } else if (token === ')') {
      level++;
    } else if (level === -1)  {
      sum += +token;
    }
  }
  return sum;
}

// Example:
console.log(sumTreeLevel("(10(5(3)(12))(14(11)(17)))", 2)); // 43