Problem overview
The function encodedTreeSums receives a tree written as a string and returns another string in the same format. Each node is a number. A node with children is followed by its children in braces, separated by commas, so 1{2{3,4},5{6}} is a root 1 with children 2 and 5, where 2 has children 3 and 4 and 5 has the child 6. Nodes can have any number of children.
In the output, every node's value is replaced by the sum of the values in its subtree, including the node itself. For the first example, the root becomes 1 + 2 + 3 + 4 + 5 + 6 = 21, the node 2 becomes 2 + 3 + 4 = 9, and 5 becomes 5 + 6 = 11. The leaves keep their values. The result is 21{9{3,4},11{6}}.
The second example, 1{1,1{1,1,1},1}, gives 7{1,4{1,1,1},1}: the middle child has three leaf children, so its sum is 1 + 3 = 4, and the root adds 1 + 4 + 1 + 1.
Approach: parse and compute in one pass
The string has a recursive grammar: a node is a number, optionally followed by {, a comma-separated list of nodes, and }. A recursive descent parser mirrors that grammar with one function that reads one node. When it meets {, it calls itself once per child.
There's no need to build a tree in memory. The function can return two things for the node it just read: the subtree's sum, and the string that encodes the node with its sums. The parent adds the child's sum to its own total and keeps the child's string for the output.
The parser needs to know where it is in the input. Recursive calls consume different parts of the string, so the position must be shared: a pointer to an integer, passed to every call, serves as a cursor that all of them advance.
Step by step
The lesson gives no step list, so here is the reasoning behind the solution.
- Start the cursor at 0 in
encodedTreeSums, and callparseEncodedTreewith the string and the address of the cursor. Only the second result, the encoded string, is needed, so the sum is discarded with_. - Read the number. While the current character is a digit, multiply
valueby 10 and add the digit. This handles values with several digits, such as 12 or 305. - Start the total at that value. A leaf's sum is its own value.
- Check for a child list. If the next character is
{, step over it and read children in a loop. - Parse one child by calling the function again. Add the child's sum to
totaland append the child's encoded string tochildren. - Decide what follows the child. A comma means another child: step over it and loop. Anything else ends the list: step over the closing
}and leave the loop. - Build the output. Convert
totalto text and, if the node had children, append{, the children joined with commas, and}. - Return both values: the total for the parent to add, and the string for the parent to keep.
The solution in Go
func encodedTreeSums(input string) string {
index := 0
_, encoded := parseEncodedTree(input, &index)
return encoded
}
func parseEncodedTree(input string, index *int) (int, string) {
value := 0
for *index < len(input) && input[*index] >= '0' && input[*index] <= '9' {
value = value*10 + int(input[*index]-'0')
*index++
}
total := value
children := []string{}
if *index < len(input) && input[*index] == '{' {
*index++
for {
childSum, childTree := parseEncodedTree(input, index)
total += childSum
children = append(children, childTree)
if *index < len(input) && input[*index] == ',' {
*index++
continue
}
if *index < len(input) && input[*index] == '}' {
*index++
}
break
}
}
encoded := strconv.Itoa(total)
if len(children) > 0 {
encoded += "{" + strings.Join(children, ",") + "}"
}
return total, encoded
}
The code uses strconv and strings, so the program needs both in its import list. In Go an unused import is a compile error, and so is a missing one.
The Go details worth a closer look:
- Bytes, not characters.
input[*index]is abyte. Comparing it with the rune constants'0'and'9'is fine, because the constants are untyped and convert tobyte. This is safe here because every character of the format is ASCII. - Digit to number.
input[*index]-'0'subtracts the code of'0'and gives 0 to 9 as abyte.int(...)converts it so it can be added to theintvalue. *index++means(*index)++. In Go,++is a statement rather than an expression and applies to the whole operand*index. It increments the integer the pointer points to, not the pointer.- Short-circuit checks.
*index < len(input) && input[*index] ...evaluates the bounds test first, and&&skips the indexing when it fails. This keeps the parser from reading past the end of the string, which would panic. - Multiple return values. The function returns an
(int, string)pair, and the caller unpacks it withchildSum, childTree := .... Discarding a result needs the blank identifier_, since unused variables are compile errors. strconv.Itoaandstrings.Join.Itoaconverts anintto its decimal text.Joinglues a slice of strings with a separator between them. Usingstring(total)instead would produce the character with that code, not the digits.- A bare
for. Go has nowhileordo;for { ... }loops untilbreakorreturn.
Complexity
Let L be the length of the input string.
Time: O(L · d), where d is the nesting depth. The cursor reads each character once, which is O(L). Building the output costs more: each node's string is made by concatenating its children's strings, so a character is copied once for every level between it and the root. A shallow tree stays close to O(L), and a deeply nested chain approaches O(L²).
Space: O(L) for the output and the intermediate strings, plus recursion depth equal to the nesting depth of the tree.
Edge cases and common mistakes
- A single leaf.
"7"gives"7": no braces are added when there are no children. - Multi-digit values.
"12{3}"gives"15{3}". Reading one character as one value would break here. - Keeping the leaves. Only the sums of internal nodes differ from the input. A leaf's subtree sum is its own value.
- Using a copy of the cursor. If the cursor were passed as an
intinstead of a pointer, each child would start from the same position as its parent and parse the same text again. - Joining with the wrong separator. The output uses commas without spaces, as in the examples.
- Empty input. An empty string produces
"0", because no digits are read and the total stays 0. The lesson's inputs always hold at least one node, so this case is outside the format.
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{3}"gives"15{3}".