LeetCode Sum Root to Leaf Numbers: DFS and BFS

Overview

Both DFS and BFS could be used to solve LeetCode Sum Root to Leaf Numbers problem, elaboration of the details are discussed here.

LeetCode Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

Analysis: DFS and BFS

1) DFS

A simple way is to use DFS, just DFS the tree and when encountering the leaf, add the value to a global sum variable.  One need to be careful about how to determine it is a leaf and don’t forget to check whether node == NULL.

One can pass the node->val as the parameter in the recursive function to make it in the stack so one don’t have to maintain the value like 1-2-3 using any external data structure. The following code implements this idea and is accepted by the LeetCode OJ to pass this Sum Root to Leaf Numbers problem:

class Solution {
    public:
        void dfs(TreeNode *root, int partial, int *sum) {
            int curr = partial * 10 + root->val;

            if (NULL == root->left && NULL == root->right) {
                *sum += curr;
                return ;
            }
            if (root->left)
                dfs(root->left, curr, sum);
            if (root->right)
                dfs(root->right, curr, sum);

        }

        int sumNumbers(TreeNode *root) {
            if (NULL == root)
                return 0;
            int sum = 0;
            dfs(root, 0, &sum);
            return sum;
        }
};

And if we are allowed to modify the original input tree node value, then we even do not need the helper dfs function and can come up with the following different implementation of dfs with simpler code:

int sumNumbers(TreeNode *root) {
            if (NULL == root)
                return 0;

            if (NULL == root->left && NULL == root->right)
                return root->val;

            if (root->left)
                root->left->val += root->val * 10;
            if (root->right)
                root->right->val += root->val * 10;
            return sumNumbers(root->left) + sumNumbers(root->right);
        }

2) BFS

Another alternative is to do iterative implementation. Two choices: using explicit stack to implement the DFS or actually preorder traversal (see “LeetCode Binary Tree Preorder Traversal: Iterative Using Stack” for further reference) in an iterative manner.

The other choice is to do BFS. Essentially, BFS does the same thing as what DFS does and BFS is more natural from the iterative sense, so I give the BFS implementation here too:

int sumNumbers(TreeNode *root) {
    if (NULL == root)
        return 0;

    queue<TreeNode *> q;
    q.push(root);

    int sum = 0;
    while (!q.empty()) {
        TreeNode *curr = q.front();
        q.pop();

        if (NULL == curr->left && NULL == curr->right)
            sum += curr->val;

        if (curr->left) {
            curr->left->val += curr->val * 10;
            q.push(curr->left);
        }
        if (curr->right) {
            curr->right->val += curr->val * 10;
            q.push(curr->right);
        }
    }
    return sum;
}

Note you can use extra data to store the value rather than modifying the original node value.

Summary

Both DFS and BFS could be used to solve LeetCode Sum Root to Leaf Numbers problem, elaboration of the details are discussed here.

Written on February 21, 2013