Problem overview
The method EncodedTreeSums receives a tree written as a string. A node is a number, optionally followed by its children in curly braces and separated by commas: "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.
The method must replace every node's value with the sum of the values in its subtree (the node itself plus all its descendants) and return the new tree in the same format. For the example, node 2 becomes 2 + 3 + 4 = 9, node 5 becomes 5 + 6 = 11, and the root becomes 1 + 9 + 11 = 21, which is the sum of all six numbers. The result is "21{9{3,4},11{6}}". Leaves keep their value, because their subtree is just themselves.
Nodes can have any number of children, and values can have several digits.
Approach: parse and compute in one pass
The string is a recursive structure: a node contains a list of nodes. That suggests a recursive-descent parser, a function that reads one node starting at the current position, calling itself for each child.
Each call does three things:
- reads the digits at the current position to get the node's own value;
- if a
{follows, parses the children one after another, adding each child's subtree sum to a running total; - builds the node's output text: its total, followed by its children's output texts in braces.
So one call returns two things: the subtree sum, which the parent needs, and the rewritten text, which the parent embeds in its own text. A shared position tracks where the parser is in the input. When a child call finishes, the position sits right after that child, so the parent can look at the next character: a comma means another child, a closing brace means the list is over.
Take "1{1,1{1,1,1},1}". The root reads 1, then the children: a leaf 1, a node 1 with three leaves (total 4), and a leaf 1. The root total is 1 + 1 + 4 + 1 = 7, giving "7{1,4{1,1,1},1}".
Step by step
Here is how the code is built, in order.
- Start the position at 0 in
EncodedTreeSumsand call the parser. Only the text half of its result,Item2, is returned. - Read the value. While the current character is a digit, multiply the value so far by 10 and add the new digit. This handles numbers like 42 or 100.
- Start the total at the node's own value and prepare an empty list of children texts.
- Check for children. If the next character is
{, step over it and enter a loop. If not, the node is a leaf and the loop is skipped. - Parse a child with a recursive call, add its sum to the total and keep its text.
- Look at the separator. A comma means another child follows, so step over it and repeat. Otherwise, step over a closing brace if there is one and leave the loop.
- Build the text. Use the total, and when there are children, add the children's texts joined by commas inside braces.
- Return both values as a tuple.
The solution in C#
class Solution {
public string EncodedTreeSums(string input) {
int index = 0;
return ParseEncodedTree(input, ref index).Item2;
}
private (int, string) ParseEncodedTree(string input, ref int index) {
int value = 0;
while (index < input.Length && char.IsDigit(input[index])) {
value = value * 10 + (input[index] - '0');
index++;
}
int total = value;
List<string> children = new List<string>();
if (index < input.Length && input[index] == '{') {
index++;
while (true) {
(int childSum, string childTree) = ParseEncodedTree(input, ref index);
total += childSum;
children.Add(childTree);
if (index < input.Length && input[index] == ',') {
index++;
continue;
}
if (index < input.Length && input[index] == '}') {
index++;
}
break;
}
}
string encoded = total.ToString();
if (children.Count > 0) {
encoded += "{" + string.Join(",", children) + "}";
}
return (total, encoded);
}
}
C# details worth knowing:
ref int index. Anintis passed by value, so a plain parameter would give each call its own copy. Withref, the callee and the caller share one variable, and the keyword must appear at both the declaration and the call:ref index. After a child call returns, the caller'sindexhas moved past the child.- Tuples. The return type
(int, string)is a value tuple. Without names, its parts areItem1andItem2. The line(int childSum, string childTree) = ...deconstructs the tuple into two new variables. - Digit to number. A
charis a number underneath, and the digit characters are consecutive, soinput[index] - '0'gives the digit's value as anint.char.IsDigittells whether the character is a digit. - Strings. Strings are immutable, so
encoded += ...creates a new string.string.Join(",", children)glues a list of strings together with a separator and adds nothing at the ends. - Bounds checks. Each
input[index]is guarded byindex < input.Length. Reading past the end of a string throwsIndexOutOfRangeException, and&&skips the second test when the first is false.
Complexity
Time: every character of the input is read once by the parser, so the parsing is linear in the length of the string. Building the output text costs more than that in the worst case: each node's text is copied into its parent's text, and so on up to the root, so a very deep tree makes the copying O(n * depth) in total. For typical inputs this is small.
Space: the recursion depth equals the depth of the tree, and the texts being built take space proportional to the input. A very deep tree would use a lot of stack, so the approach suits trees of moderate depth.
Edge cases and common mistakes
- Multi-digit values.
"10{20}"gives"30{20}". Reading only one character per value would fail here. - A single leaf.
"42"returns"42". No braces are added, becausechildrenis empty. - Any number of children. The loop continues while commas follow, so a node can have one child or many.
- Not moving past separators. If the comma or the closing brace isn't consumed, the parent's parse position is wrong and later siblings are misread.
- Passing the index by value. Without
ref, the caller's position never advances and the same child would be parsed again and again. - Adding the node's own value twice or not at all. The total starts at the node's own value, and each child contributes its full subtree sum exactly once.
- Using the original child values. The parent adds the child's subtree sum, not the number written in the input.
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}"."42"gives"42"."10{20}"gives"30{20}".