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

Question

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.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:

1. 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.

2. 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.

Answer 1

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(n2) 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(n2) 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 2).
• 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:

n2 + (n-3)2 + (n-6)2 + ... + (n-3k)2

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

Cubic runtime complexity

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

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

• Igor Soloydenko: What tool did you use to generate the complexity chart?
• le_m: @IgorSoloydenko plot.ly - the data doesn't result from a runtime evaluation however, but simply from counting 'primitive' operations according to the model of computation.

Answer 2

Some notes, in no particular order:

• If there are unbalanced/missing parentheses, you print an error to the console. However, I'd say you should just throw an exception instead. If the parentheses don't make sense, there's something wrong, and probably no way to recover.

• This stood out:

  input = input.substr(1);
  input = input.substring(0, input.length - 1);
  

  Why use both substr and substring? The two are very subtly different, so don't mix them unless you have good reason. And why do the trimming in two passes? You could just slice from 1 to length-1 (or length-2 in the case of substr, since they're different) in one go.

• This stood out too:

  totalValue += JSON.parse(currentValue.val);
  

  Use parseInt, parseFloat, or even * 1 (in a pinch) to convert the string to a number. JSON ain't got nothing to do with this.

• getCurrentVal could be made simpler with a regular expression like /^\d+/ that matches digits only.

Now, if the idea is only to sum the nodes at each level, you can actually skip a lot of stuff.

Namely, there's no reason to build a graph. You can just read the string from beginning to end, and get the sums:

function sumLevels(string) {
 var sums = [],
 level = -1;
 for(let i = 0; i < string.length; i++) {
 if(string[i] === '(') {
 level += 1; // add a level for each open paren
 } else if(string[i] === ')') {
 level -= 1; // remove a level for each closing paren
 } else {
 // match one or more digits
 let match = string.slice(i).match(/^\d+/);
 // complain if there are no digits
 if(!match) throw new Error(`Parse error at char ${i}`);
 // fast-forward the loop counter
 i += match[0].length - 1;
 // add to sum for current level
 sums[level] = (sums[level] || 0) + parseInt(match[0], 10);
 }
 }
 return sums;
}

For the test string you had, the function returns [ 10, 19, 43 ]; the sum at each level.

Note, though that the above doesn't do much input checking. It doesn't, for instance, check that parentheses are balanced, meaning level could go negative or skip ahead, which wouldn't make sense. However, checking could be added without too much trouble. I'll leave that as an exercise for the reader though.

Incidentally, another way to write the above, using replace as a regex scan-like function, would be:

function sumLevels(string) {
 var sums = [],
 level = -1;
 string.replace(/(\(|\)|\d+)/g, (_, token) => {
 switch(token) {
 case '(':
 level += 1;
 break;
 case ')':
 level -= 1;
 break;
 default:
 sums[level] = (sums[level] || 0) + parseInt(token, 10);
 }
 });
 return sums;
}

This has even less input-checking, though.

• Hodrobond: Thank you very much, this is the exact type of feedback I was looking for, it is very much appreciated. I'll be rereading over this in the next few days in order to ensure I understand everything, but thanks again!