Leetcode.com problem 129: "Sum Root to Leaf Numbers"

Leetcode.com problem 129: Sum Root to Leaf Numbers

James S. Plank

Mon Apr 10 15:25:05 EDT 2023

Problem Statement.
Success Rate (as of April, 2023): 61.1%
This is a "medium" problem.
tests.sh: A testing script
answers.txt: Correct output to the testing script
A skeleton with my main() that you can use to test your answer.
A solution that uses a preorder traversal.

In case Leetcode's servers are down

You have the following definition of a TreeNode, which stores a node in a binary tree:

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

In case those last three lines look a little confusing to you, those are three constructors: You can construct a tree node with a value of 0 and no children, a tree node with a given value and no children, or a tree node with a given value and given children.

Your job is to write the method sumNumbers in the class Solution, with the following prototype:

class Solution {
  public:
    int sumNumbers(TreeNode *root);
};

Here's a description of the tree and what sumNumbers() should produce:

root is the root of a binary tree.
Each node in the tree has a val between 0 and 9.
You are to consider each path from the root to a leaf node as a number, whose digits are represented by the vals in each node from the root to the leaf.
sumNumbers() should return the sum of the numbers of all paths from the root to a leaf node.
The tree will have between 1 and 1000 nodes.
The answer is guaranteed to fit into a 32-bit signed integer.

So, here are three examples in ASCII art:

Answer = 53 + 56 = 109.

Answer = 23 + 241 + 240 = 504

Answer = 241 + 240 + 23 = 504

Driver program and testing

The driver program in Skeleton.cpp reads a Tree on standard input by reading numbers:

First the value of the root
Then the values of the two children of the root (the two nodes at level 1)
Then the values of the four children of those children (the four nodes at level 2)
And so on. You don't need to complete the last level.

If there is no node, then a value of -1 should be specified. So, here are the three examples above:

UNIX> cat example-1.txt
5
3 6
UNIX> cat example-2.txt
2
3 4
-1 -1 1 0          # We need two -1's to take the place of the two children of node 3.
UNIX> cat example-3.txt
2 4 3 1 0          # Formatting doesn't matter
UNIX>

I'm not going to go over the code, but you should take a read if you're interested. I have bigger example files in the other example-x.txt files:

UNIX> wc example-*.txt
       2       3       6 example-1.txt
       3       7      16 example-2.txt
       1       5      10 example-3.txt
      20      20      40 example-4.txt
       1      31      79 example-5.txt
       1      63     136 example-6.txt
       1     250     534 example-7.txt
       1     500    1249 example-8.txt
       1    1000    2295 example-9.txt
      31    1879    4365 total
UNIX>

Let's look at the nodes first

Before we solve the problem, let's just write code that prints out each node, the values of its children, and then recursively calls itself on chidlren when they are non-null. The code is in Print-Nodes.cpp. Here is the implementation of sumNumbers():

/* We're not going to solve the problem.  Instead, we're going to simply print
   out each node and the vals of its two children (-1 if the child is nullptr). */

int Solution::sumNumbers(TreeNode *root)
{
  printf("Node: %d   Left: %d    Right: %d\n", 
          root->val,
          (root->left == nullptr) ? -1 : root->left->val,
          (root->right == nullptr) ? -1 : root->right->val);
   
  if (root->left != nullptr) (void) sumNumbers(root->left);
  if (root->right != nullptr) (void) sumNumbers(root->right);
  return 0;
}

We run this on our examples above, and on example-9.txt to confirm that it's reading the trees correctly, and to show that example-9.txt has 706 nodes:

UNIX> g++ Print-Nodes.cpp
UNIX> a.out < example-1.txt
Node: 5   Left: 3    Right: 6
Node: 3   Left: -1    Right: -1
Node: 6   Left: -1    Right: -1
0
UNIX> a.out < example-2.txt
Node: 2   Left: 3    Right: 4
Node: 3   Left: -1    Right: -1
Node: 4   Left: 1    Right: 0
Node: 1   Left: -1    Right: -1
Node: 0   Left: -1    Right: -1
0
UNIX> a.out < example-3.txt
Node: 2   Left: 4    Right: 3
Node: 4   Left: 1    Right: 0
Node: 1   Left: -1    Right: -1
Node: 0   Left: -1    Right: -1
Node: 3   Left: -1    Right: -1
0
UNIX> a.out < example-9.txt | wc       # This shows that there are 706 nodes in the example (the last line, which is a zero, doesn't correspond to a node).
     707    4237   21889
UNIX>

Answer the following question to yourself: Is this a preorder or a postorder traversal? The answer is preorder, because we print before we do the recursion.

Solving his with a preorder traversal

Each node in the graph represents a number. For our three examples, we can show these numbers:

Can you see a pattern? Each number is equal to its parent's number times ten, plus its val. So we can do a preorder traversal, where we define the following method:

int Preorder(TreeNode *n, int parent_number);

The code in sumNumbers simply calls this with the root and zero:

int Solution::sumNumbers(TreeNode *root)
{
  return Preorder(root, 0);
}

And here's the code for Preorder():

/* Here's the preorder traversal.  Calculate the node's number, and then either
   return it (if you have no children). Or sum the values of your children. */

int Solution::Preorder(TreeNode *n, int parent_number)
{
  int number, rv;

  /* Calculate the number and return it if you are a leaf node. */

  number = parent_number * 10 + n->val;
  if (n->left == nullptr && n->right == nullptr) return number;

  /* Otherwise, sum the numbers of your children and return that. */

  rv = 0;
  if (n->left != nullptr) rv += Preorder(n->left, number);
  if (n->right != nullptr) rv += Preorder(n->right, number);
  return rv;
}