Home
Depth First Search and Breadth First Search Algorithm to Sum Root to Leave Numbers in Binary Tree
Tags:, , , ,

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

April 9, 2016 No Comments algorithms, BFS, c / c++, DFS, recursive

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

/**
 * 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);
    }
};
/**
 * 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. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

/**
 * 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;
    }
};
/**
 * 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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;
    }
};
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) —

GD Star Rating
loading...
719 words
Last Post: How to Check Symmetric Tree in C++ (Iterative and Recursion)?
Next Post: C++ Coding Exercise - Gas Station

The Permanent URL is: Depth First Search and Breadth First Search Algorithm to Sum Root to Leave Numbers in Binary Tree

Related posts:

  1. Fixing Profile Query Command due to API Change in Steem Blockchain Due to an API change in SteemIt see this post, the following code to get...
  2. Teaching Kids Programming – Closest Binary Search Tree Value (Recursion + Inorder Traversal + Binary Search Algorithm) Teaching Kids Programming: Videos on Data Structures and Algorithms Given the root of a binary...
  3. How to Determine Sum of Two Square Numbers? Given a non-negative integer c, your task is to decide whether there’re two integers a...
  4. The Secure Shell (SSH) Chrome Extension developed by Google Speaking about SSH tools, we often use the PuTTY or Termius, which are heavy weight...
  5. Algorithms to Determine a Palindrome Number Determine whether an integer is a palindrome. An integer is a palindrome when it reads...
  6. How to Find the Kth Smallest Element in a BST Tree Using Java/C++? Given a binary search tree, write a function kthSmallest to find the kth smallest element...
  7. C++ Algorithm to Remove Outermost Parentheses A valid parentheses string is either empty (“”), “(” + A + “)”, or A...
  8. You need a Numeric Keypad to Start with Your HHKB! Getting a HHKB and being excited for a few days? Sooner or later, you ‘ll...

Leave a Reply