Return to Answer

• 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).

• 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).

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

// 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)
 };
}

// Sum integer tree nodes at given level: 
function sumTreeLevel(tree, level) {
 let tokens = tree.match(/(\(|[0-9]+|\))/g);
 let nesting = -1;
 let sum = 0;
 for (let token of tokens) {
 if (token === '(') {
 nesting++;level--;
 } else if (token === ')') {
 nesting--;level++;
 } else if (nestinglevel === level-1) {
 sum += +token;
 }
 }
 return sum;
}
// Example:
console.log(sumTreeLevel("(10(5(3)(12))(14(11)(17)))", 2)); // 43