Depth First Search and Breadth First Search Algorithm to Sum Root to Leave Numbers in Binary Tree

justyy (82)in #programming • 4 years ago

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.

This is also a tree-related puzzle, so similarly to this, we use a recursion and a iterative approach.

Recursion

The key thing to solve here is how to get the value from the root to one leaf. We need a helper function which takes a Node and a previous sum. So when recursively calling the function in the next level, we multiple the previous sum by ten and add the node value.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int getValue(TreeNode* node, int x) {
        if (node == NULL) {
            return 0;
        }
        int prev = x * 10 + node->val;
        if ((node->left == NULL) && (node->right == NULL)) {
            return prev;
        }
        return getValue(node->left, prev) + getValue(node->right, prev);
    }
    int sumNumbers(TreeNode* root) {
        return getValue(root, 0);
    }
};

The terminal conditions: if the node is NULL, the value is zero; if the node is a leaf node, we return the previous sum. Otherwise, simply add the sums of both sub trees, left and right. Recursion implements the DFS (Depth First Search).

Here is another DFS implementation that utilities the function (lambda) from functional header.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int sumNumbers(TreeNode* root) {
        int res = 0;
        function<void(TreeNode*, int)> dfs = [&](TreeNode* root, int cur) {
            if (!root) {
                return;
            }
            if (root->left == root->right) {
                res += cur * 10 + root->val;
                return;
            }
            dfs(root->left, cur * 10 + root->val);
            dfs(root->right, cur * 10 + root->val);
        };
        dfs(root, 0);
        return res;
    }
};

We also can use simple comparion root->left == root->right to check for NULL - this is not absolutely true but it is ok to pass all test cases.

Iterative

This puzzle can be solved using BFS (Breadth First Search). For example, we first explore the tree at level 1 and then explore the nodes at level 2 .. until we get to the point of leaves. When we are visiting a node, we add the node value to the previous sum and add the node-value pair to the queue. At the leaves, we need to add all the values.

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        if (root == NULL) {
            return 0;
        }
        queue<pair<TreeNode*, int>> q;
        q.push(make_pair(root, root->val));
        int r = 0;
        while (!q.empty()) {
            pair<TreeNode*, int> p = q.front();
            q.pop();
            TreeNode* cur = p.first;
            if ((cur->left == NULL) && (cur->right == NULL)) {
                r += p.second;
                continue;
            }
            if (cur->left != NULL) {
                q.push(make_pair(cur->left, p.second * 10 + cur->left->val));
            }
            if (cur->right != NULL) {
                q.push(make_pair(cur->right, p.second * 10 + cur->right->val));
            }
        }
        return r;
    }
};

Similar BFS code can be used to solve similar tree problems such as this.

--EOF (The Ultimate Computing & Technology Blog) --