Problem overview
The method encodedTreeSums receives a tree written as a string and returns another string with the same shape. In the input, a node is its number, optionally followed by its children in curly braces and separated by commas. So "1{2{3,4},5{6}}" is a root 1 with two children: 2, which has children 3 and 4, and 5, which has the single child 6. A node can have any number of children.
In the output, every number is replaced by the sum of all values in that node's subtree, the node included. For the first example, 2's subtree has 2 + 3 + 4 = 9, 5's has 5 + 6 = 11, and the root has 1 + 9 + 11 = 21. The result is "21{9{3,4},11{6}}". A leaf keeps its value, since its subtree is just itself. The second example, "1{1,1{1,1,1},1}", gives "7{1,4{1,1,1},1}".
Approach: parse and sum in one pass
The text has a recursive grammar: a node is a number, and if a { follows, a comma-separated list of nodes and a closing }. A function that reads one node can call itself for every child it finds. That is a recursive descent parser, and it needs no explicit tree at all.
Each call reads one node and returns two things: the sum of its subtree and the new text for it. The sum is built from the node's own number plus the sums returned by its children. The text is that sum, followed by the children's new texts joined by commas inside braces, when there are children.
All the calls must share one reading position, so the string is consumed from left to right and every call continues where the previous one stopped. The lesson keeps that position in a one-element array, index, which each call can both read and change.
Tracing "1{2{3,4},5{6}}": the first call reads the number 1, sees {, and starts reading children. The first child reads 2, sees {, and reads 3 and 4 as leaves, each time stopping at a comma or at the closing brace. It returns the sum 9 and the text "9{3,4}". The second child returns 11 and "11{6}". The root adds 1 + 9 + 11 and returns "21{9{3,4},11{6}}".
Step by step
The lesson has no written steps for this problem, so here is the logic of the reference solution in order.
- Create the shared position.
encodedTreeSumsmakesArray(0), a one-element array holding the index of the next unread character, and passes it to the parser. - Return the text part. The parser returns a pair of the sum and the new text, and
._2picks the text. - Read the node's number. While the current character is a digit, multiply
valueby 10 and add the digit. This handles numbers with several digits. The checkindex(0) < input.lengthcomes first, so the loop never reads past the end of the string. - Start the sum and the child list. The total begins as the node's own value, and the new texts of the children will be collected in a buffer.
- Look for an opening brace. If the current character is
{, skip it. Otherwise the node is a leaf, and nothing more is read. - Read the children in a loop. Each iteration calls the parser for one child, adds the child's sum to
totaland stores the child's text. - Decide how to continue. A comma means another child follows, so it is skipped and the loop goes on. Anything else ends the list. If the character is the closing brace, it is skipped too, and the flag
morebecomesfalse. - Build the text. It starts as
total.toString. If there were children,"{", the children joined by","and"}"are appended. - Return both. The pair
(total, encoded)goes back to the caller, which either uses the sum for its own total or, at the top, keeps only the text.
The solution in Scala
class Solution {
def encodedTreeSums(input: String): String = {
val index = Array(0)
parseEncodedTree(input, index)._2
}
def parseEncodedTree(input: String, index: Array[Int]): (Int, String) = {
var value = 0
while (index(0) < input.length && input(index(0)).isDigit) {
value = value * 10 + (input(index(0)) - '0')
index(0) += 1
}
var total = value
val children = scala.collection.mutable.ArrayBuffer[String]()
if (index(0) < input.length && input(index(0)) == '{') {
index(0) += 1
var more = true
while (more) {
val (childSum, childTree) = parseEncodedTree(input, index)
total += childSum
children += childTree
if (index(0) < input.length && input(index(0)) == ',') {
index(0) += 1
} else {
if (index(0) < input.length && input(index(0)) == '}') {
index(0) += 1
}
more = false
}
}
}
var encoded = total.toString
if (children.nonEmpty) {
encoded += "{" + children.mkString(",") + "}"
}
(total, encoded)
}
}
The Scala details worth a closer look:
- A one-element array as a shared cursor. An
Intparameter is passed by value, so a callee can't move the caller's position. AnArray[Int]is a mutable object, and every call sees the same one, soindex(0) += 1in a deep call moves the position for everyone. Thevalonly fixes which arrayindexrefers to, and the element inside can still change. - Strings are indexed with round brackets.
input(i)returns aChar.isDigittests it, andinput(i) - '0'subtracts two characters, which gives anIntfrom 0 to 9. - A method can return a tuple. The return type
(Int, String)is a pair, and the last line(total, encoded)builds one.._2reads its second part, andval (childSum, childTree) = ...unpacks both parts into two names at once. &&short-circuits. Inindex(0) < input.length && input(index(0)).isDigit, the second test runs only if the first is true, which prevents an index error at the end of the string.+=on avarand on a buffer.total += childSumandencoded += ...reassign avar, whilechildren += childTreeappends to a mutable buffer.mkString(",")joins its elements with commas.- Recursion defined later in the class.
encodedTreeSumscallsparseEncodedTreebefore its definition. Members of a class can be used in any order.
Complexity
Time. Every character of the input is read once, so parsing is O(n) for a string of length n. Building the output adds the cost of copying: each node's text is copied into its parent's text, so a character near the bottom of a deep tree is copied once per ancestor. That makes the total O(n * d) for a tree of depth d. For a balanced tree that is small, and for a tree that is one long chain it approaches O(n²).
Space: O(n). The output text has about the length of the input, and the recursion goes as deep as the tree does.
Edge cases and common mistakes
- A single leaf.
"5"gives"5". There is no brace, so the node keeps its value and gets no children. - Several digits.
"12{3}"gives"15{3}". Reading one character as a number would give wrong sums. - Deep nesting.
"10{20{30}}"gives"60{50{30}}". Each ancestor includes everything below it. - More than two children.
"1{2,3,4}"gives"10{2,3,4}", because the loop continues for as long as a comma follows. - Adding the node's own value twice.
totalstarts as the node's value, and only the children's sums are added after that. - Forgetting to skip the separators. If the comma or the closing brace is not consumed, the next call starts on a character that is not a digit, reads the value 0 and stays at the same position, so the loop keeps adding zero-valued children and never ends.
- Using a plain
Intposition. A copy of the position inside a callee is lost when it returns, and the caller would read the same characters again. - Size of the sums. The sums are
Intvalues, so a tree whose total goes beyond 2,147,483,647 wraps around without any error.
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}"."5"gives"5"."12{3}"gives"15{3}"."10{20{30}}"gives"60{50{30}}".
