Calculate the sum at a level of a binary tree represented in a String

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] !== "(" && input[0] !== ")" && 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 < 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