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 ²).
• 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 ²).
• 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)
  };
}