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] !== "(" && input[0] !== ")" && 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 > 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 > 0){
if(children.left.leng

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

StackExchange Code Review Q#162850, answer score: 3