Problem overview
The method encodedTreeSums receives a tree written as a string and returns another string in the same format. A node is written as its value, followed by its children in curly braces and separated by commas if it has any: 1{2{3,4},5{6}} is a node 1 with two children, 2 (with children 3 and 4) and 5 (with one child, 6). A node can have any number of children.
In the output, every node's value is replaced by the sum of the values in its whole subtree, itself included. For the first example, node 2 becomes 2 + 3 + 4 = 9, node 5 becomes 5 + 6 = 11, and the root becomes 1 + 9 + 11 = 21, which gives 21{9{3,4},11{6}}. Leaves keep their value, because their subtree is just themselves. 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
There is no tree object here, only text. One option is to parse the string into nodes, compute the sums, and print the nodes again. The lesson does all three in one recursive function instead: reading a node returns both the sum of its subtree and the already encoded output text for it.
The format is itself recursive: a node is a number, optionally followed by {, a comma-separated list of nodes, and }. A function that reads one node by reading a number and then calling itself for each child follows that grammar directly. This technique is called recursive descent.
For a node, the function needs to:
- read the digits of its value;
- if a
{follows, read child after child, adding each child's sum to its own total, until the closing}; - return the total together with the text
totalortotal{child,child,...}.
Each child's text is built before the parent's, because the parent's number is only known after all its children have been read. That is why the function returns finished strings from the bottom up.
Step by step
- Keep a position.
encodedTreeSumscreatesindex, a one-element array holding 0, and hands it to every call. The recursive calls need to see how far the previous ones read, and a plain number parameter would be copied into each call, so a change would not reach the caller. - Read the value. While the current character is a digit, multiply the value so far by 10 and add the digit, obtained as its character code minus 48 (the code of
'0'). This handles values with several digits, such as 12. Each step also checks that the position is still inside the string. - Start the total at the node's own value and prepare an empty list of child texts.
- Look for children. If the next character is
{, step over it. - Read the children in a loop. Each iteration calls
parseEncodedTreeagain, adds the returned sum tototal, and stores the returned text. - Decide how to continue. A comma means another child follows: step over it and read the next one. Otherwise, step over a closing
}if there is one, and leave the loop. - Build the output text. It starts as the total converted to a string. When there were children, append the child texts joined by commas inside braces.
- Return the pair
[total, encoded]. The top-level method returns the second element, the text.
The solution in TypeScript
class Solution {
encodedTreeSums(input: string): string {
const index: number[] = [0];
return this.parseEncodedTree(input, index)[1];
}
parseEncodedTree(input: string, index: number[]): [number, string] {
let value = 0;
while (index[0] < input.length && input[index[0]] >= '0' && input[index[0]] <= '9') {
value = value * 10 + (input.charCodeAt(index[0]) - 48);
index[0]++;
}
let total = value;
const children: string[] = [];
if (index[0] < input.length && input[index[0]] === '{') {
index[0]++;
while (true) {
const [childSum, childTree] = this.parseEncodedTree(input, index);
total += childSum;
children.push(childTree);
if (index[0] < input.length && input[index[0]] === ',') {
index[0]++;
continue;
}
if (index[0] < input.length && input[index[0]] === '}') {
index[0]++;
}
break;
}
}
let encoded = total.toString();
if (children.length > 0) {
encoded += "{" + children.join(",") + "}";
}
return [total, encoded];
}
}
TypeScript details worth knowing:
- The array as a shared cursor. Numbers are passed by value, so a function that did
n++on anumberparameter would change only its own copy. An array is an object, and every call receives a reference to the same one, soindex[0]++is visible everywhere. A class field or a closure would work too. - A tuple return type.
[number, string]describes an array of exactly two elements: first a number, then a string. The destructuringconst [childSum, childTree] = ...unpacks it into two variables. At run time it is an ordinary two-element array. - Strings can be indexed.
input[index[0]]gives a one-character string. Comparing it with'0'and'9'works because single digit characters compare in the same order as the digits themselves.charCodeAtreturns the numeric code, and subtracting 48 turns'7'into 7. - Reading past the end.
input[i]beyond the length givesundefinedinstead of an error, but the code checksindex[0] < input.lengthfirst, so it never relies on that. while (true)withcontinueandbreak. The loop is left only through thebreakat its end. After a comma,continuejumps back to read the next child.+=on strings. It appends, which is why the child texts can be added toencodedwith the braces and commas.
Complexity
Time: O(n) for the parsing, where n is the length of the string: each character is read a constant number of times. Building the output costs a little more, because each node's text is copied into its parent's text, so a character that sits at depth d is copied about d times. For typical bushy trees that is negligible; for a very deep chain it approaches O(n * h), where h is the height.
Space: O(n). The output strings together are about as long as the input, and the recursion is as deep as the tree is tall, which for a tree written as a chain is proportional to n.
Edge cases and common mistakes
- A single node.
"7"has no braces, so the answer is"7". - Multi-digit values.
"12{30,4}"gives"46{30,4}". Reading only one character per value would break this. - Leaves are unchanged. Don't add anything to a leaf's text; it already equals its sum.
- Several children and commas. After the last child there is a
}, not a comma. The loop must stop there and move past it, or the parent would try to read it as another node. - Sums from the original values. Each node's sum adds its children's sums, so the numbers already include all deeper nodes. Adding the raw values would give the wrong total for anything deeper than two levels.
- A plain number as the cursor. The position would never advance in the caller, and the same characters would be read again.
- Negative values are not part of the format; the minus sign is not handled.
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,4}"gives"46{30,4}".