Problem overview
The function encodedTreeSums receives a tree written as a string and returns another string. In the format, a node is a number, optionally followed by its children in braces and separated by commas. So "1{2{3,4},5{6}}" is a root 1 with two children: 2 (with children 3 and 4) and 5 (with the single child 6).
Every number in the output is replaced by the sum of the values in that node's subtree, which includes the node itself. For the example, node 2 becomes 2 + 3 + 4 = 9, node 5 becomes 5 + 6 = 11, and the root becomes 1 + 9 + 11 = 21, whose leaves keep their own values. The result is "21{9{3,4},11{6}}". For "1{1,1{1,1,1},1}" the answer is "7{1,4{1,1,1},1}".
Approach: parse and sum in the same pass
Building a real tree and then walking it would work, but the string already has a recursive shape: a node is a number, then optionally {, a comma-separated list of nodes, and }. A function that parses one node can call itself for each child. That technique is called recursive descent parsing.
The function reads the digits of the node's value, then checks for {. If it finds one, it parses each child in turn. A child's call returns two things: the child's subtree sum and the child's finished output string. The parent adds the sums to its own value and joins the strings. The sum of a subtree is only known after all its children are parsed, so the parent builds its own output last.
Since the parser must know where to continue after a child finishes, all calls share one reading position, which every call advances as it consumes characters.
Step by step
- Keep the position in a one-element array.
encodedTreeSumscreatesintArrayOf(0)and passes it down, so every call sees the same current position. - Start the helper
parseEncodedTree, which takes the input and the position array, and returns aPairof the subtree sum and the encoded text. - Read the number. While the position is inside the string and the current character is a digit, multiply
valueby 10 and add the digit. This handles values with several digits, such as 12. - Start
totalatvalueand create an empty list for the children's output strings. - Check for
{. A leaf has no braces, so it skips the children entirely. - Parse the children in a loop. Step past
{, parse one child, add its sum tototaland keep its string. Then, if the next character is,, step past it and parse another child. - Close the group. When the next character isn't a comma, skip the
}if it is there and leave the loop. - Build the output. The text starts as
totalconverted to a string. When there are children, append{, the children joined with commas, and}. - Return the pair of the total and the text. At the top level,
encodedTreeSumstakes the second part.
The solution in Kotlin
class Solution {
fun encodedTreeSums(input: String): String {
val index = intArrayOf(0)
return parseEncodedTree(input, index).second
}
fun parseEncodedTree(input: String, index: IntArray): Pair<Int, String> {
var value = 0
while (index[0] < input.length && input[index[0]].isDigit()) {
value = value * 10 + (input[index[0]] - '0')
index[0]++
}
var total = value
val children = mutableListOf<String>()
if (index[0] < input.length && input[index[0]] == '{') {
index[0]++
while (true) {
val (childSum, childTree) = parseEncodedTree(input, index)
total += childSum
children.add(childTree)
if (index[0] < input.length && input[index[0]] == ',') {
index[0]++
continue
}
if (index[0] < input.length && input[index[0]] == '}') {
index[0]++
}
break
}
}
var encoded = total.toString()
if (children.isNotEmpty()) {
encoded += "{" + children.joinToString(",") + "}"
}
return Pair(total, encoded)
}
}
The Kotlin details worth a closer look:
- Why an
IntArrayfor the position. A Kotlin parameter is read-only, and anIntpassed to a function is copied, so a helper can't advance its caller's counter. An array is an object, so every call shares its elementindex[0]. - Char arithmetic.
input[i]is aChar. Subtracting'0'from a digit character gives anIntfrom 0 to 9, because characters are numbered consecutively.isDigit()tests the character first. - Destructuring.
val (childSum, childTree) = ...unpacks aPairinto two variables, in the order of itsfirstandsecondproperties. - Short-circuit checks.
index[0] < input.length && ...tests the bound first, soinput[index[0]]is never read past the end of the string. - Building text.
joinToString(",")joins the list with commas and no trailing comma.+=on aStringvarcreates a new string. - Int sums. Sums use 32-bit
Int, so totals above 2,147,483,647 would wrap around silently.
Complexity
Let n be the length of the input.
Time. Every character is read once, which is O(n). Building the output strings adds copying: a node's text is copied into its parent's, and that into the grandparent's, so each character is copied once per level above it. The total is O(n) for a shallow tree and up to O(n²) for a very deep one, such as 1{1{1{1{...}}}}.
Space: O(n) for the strings, plus the recursion depth, which equals the depth of the tree.
Edge cases and common mistakes
- A single leaf.
"7"gives"7". - Multi-digit values.
"12{30}"gives"42{30}". Reading only one digit per node would break this. - Deep nesting.
"1{2{3{4}}}"gives"10{9{7{4}}}": each level adds its own value to the sum below it. - Forgetting the shared position. If each call kept its own copy of the position, the parent would re-read the characters its child already consumed.
- Adding the wrong number. The parent adds the child's subtree sum, the first part of the pair. Adding only the child's own value would ignore its descendants, so the root of the first example would come out as 1 + 2 + 5 = 8 instead of 21.
Testing
"1{2{3,4},5{6}}"gives"21{9{3,4},11{6}}"."1{1,1{1,1,1},1}"gives"7{1,4{1,1,1},1}"."7"gives"7"."12{30}"gives"42{30}"."1{2{3{4}}}"gives"10{9{7{4}}}".