Return the Path that Sum up to Target using DFS or BFS Algorithm

Time：2020-09-17 14:26:24
Class：Weblog
Read：25

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum. Note: A leaf is a node with no children.

Example:
Given the below binary tree and sum = 22,
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1
Return:
1
2
3
4
[
   [5,4,11,2],
   [5,8,4,5]
]
[
   [5,4,11,2],
   [5,8,4,5]
]

This is yet another classic tree puzzle that can be solved via either Depth First Search (DFS) or Breadth First Search (BFS) algorithm.

Breadth First Search Algorithm of Finding Path Sum

The BFS searches the tree level-by-level, via the use of a queue. A node in the tree contains three information: the current node, the path till this point, and the remaining sum.

When the remaining sum is zero and the node is a leaf, then we push the path to the result array. While the queue still has nodes, we pop one from the queue and push its children if any to the end of the queue.

If you are using Javascript, please note that you may need to clone the path array.

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {number[][]}
 */
var pathSum = function(root, sum) {
    var ans = [];
    if (!root) return [];
    var q = [[root, [], sum]];
    while (q.length) {
        var p = q.shift();
        var cur = p[0];
        var path = p[1];
        var sum = p[2];
        sum -= cur.val;
        path.push(cur.val);
        if ((sum === 0) && (cur.left === null) && (cur.right === null)) {
            ans.push(path);
        }
        if (cur.left) q.push([cur.left, path.slice(), sum]);
        if (cur.right) q.push([cur.right, path.slice(), sum]);
    }
    return ans;
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {number[][]}
 */
var pathSum = function(root, sum) {
    var ans = [];
    if (!root) return [];
    var q = [[root, [], sum]];
    while (q.length) {
        var p = q.shift();
        var cur = p[0];
        var path = p[1];
        var sum = p[2];
        sum -= cur.val;
        path.push(cur.val);
        if ((sum === 0) && (cur.left === null) && (cur.right === null)) {
            ans.push(path);
        }
        if (cur.left) q.push([cur.left, path.slice(), sum]);
        if (cur.right) q.push([cur.right, path.slice(), sum]);
    }
    return ans;
};

The following is a C++ implementation of the BFS algorithm where we use a std::tuple to store more than two information in a node. If there are two types of information, we can use std::pair instead.

/**
 * 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:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> r;
        if (!root) return r;
        queue<tuple<TreeNode*, vector<int>, int>> Q;
        Q.push({root, {}, sum});
        while (!Q.empty()) {
            auto p = Q.front();
            Q.pop();
            TreeNode* cur = std::get<0>(p);
            vector<int> path = std::get<1>(p);
            int curSum = std::get<2>(p);
            curSum -= cur->val;
            path.push_back(cur->val);
            if (curSum == 0) {
                if ((cur->left == nullptr) && (cur->right == nullptr)) {
                    r.push_back(path);
                }
            } 
            if (cur->left != nullptr) Q.push({cur->left, path, curSum});
            if (cur->right != nullptr) Q.push({cur->right, path, curSum});
        }
        return r;
    }
};

/**
 * 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:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> r;
        if (!root) return r;
        queue<tuple<TreeNode*, vector<int>, int>> Q;
        Q.push({root, {}, sum});
        while (!Q.empty()) {
            auto p = Q.front();
            Q.pop();
            TreeNode* cur = std::get<0>(p);
            vector<int> path = std::get<1>(p);
            int curSum = std::get<2>(p);
            curSum -= cur->val;
            path.push_back(cur->val);
            if (curSum == 0) {
                if ((cur->left == nullptr) && (cur->right == nullptr)) {
                    r.push_back(path);
                }
            } 
            if (cur->left != nullptr) Q.push({cur->left, path, curSum});
            if (cur->right != nullptr) Q.push({cur->right, path, curSum});
        }
        return r;
    }
};

Depth First Search Algorithm of Finding Path Sum

The DFS often finds a path quicker than the BFS. And a DFS is often implemented as a recursion. See below local recursive function dfs in Javascript solution.

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {number[][]}
 */
var pathSum = function(root, sum) {
    var ans = [];
    function dfs(root, arr, s) {
        if (!root) return;
        arr.push(root.val);
        s -= root.val;
        if ((s === 0) && (root.left === null) && (root.right === null)) {
            ans.push(arr);
            return;
        }
        if (root.left) dfs(root.left, arr.slice(), s);
        if (root.right) dfs(root.right, arr.slice(), s);
    }
    dfs(root, [], sum);
    return ans;
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {number[][]}
 */
var pathSum = function(root, sum) {
    var ans = [];
    function dfs(root, arr, s) {
        if (!root) return;
        arr.push(root.val);
        s -= root.val;
        if ((s === 0) && (root.left === null) && (root.right === null)) {
            ans.push(arr);
            return;
        }
        if (root.left) dfs(root.left, arr.slice(), s);
        if (root.right) dfs(root.right, arr.slice(), s);
    }
    dfs(root, [], sum);
    return ans;
};

Similarly, the C++ DFS implementation is done via recursion.

/**
 * 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:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> r;
        dfs(r, {}, root, sum);
        return r;
    }
    
private:
    void dfs(vector<vector<int>> &r, vector<int> cur, TreeNode* root, int sum) {
        if (root == nullptr) return;
        sum -= root->val;
        cur.push_back(root->val);
        if ((sum == 0) && (root->left == nullptr) && (root->right == nullptr)) {
            r.push_back(cur);
        } else {
            dfs(r, cur, root->left, sum);
            dfs(r, cur, root->right, sum);            
        }
    }
};

/**
 * 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:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> r;
        dfs(r, {}, root, sum);
        return r;
    }
    
private:
    void dfs(vector<vector<int>> &r, vector<int> cur, TreeNode* root, int sum) {
        if (root == nullptr) return;
        sum -= root->val;
        cur.push_back(root->val);
        if ((sum == 0) && (root->left == nullptr) && (root->right == nullptr)) {
            r.push_back(cur);
        } else {
            dfs(r, cur, root->left, sum);
            dfs(r, cur, root->right, sum);            
        }
    }
};

All four implementations run at O(N) time and O(N) space, where N is the number of nodes in the tree.

–EOF (The Ultimate Computing & Technology Blog) —

Recommend：
How to Write Fresh Blog Content After Years on the Job
5 Clean Energy Blogs to Read in 2019
Social Media is Dying. Here are 3 Ways to Hack it for More Traff
5 Skills All Successful Content Writers Have Mastered
Blogging for Dummies in 2019: The Only Cheat Sheet You Need
Are Readers Reaching Your Call To Action?
How to Manage a Content Marketing Plan for Your Blog
4 Simple Techniques To Bring Your Dead Blog Back To Life
How to Earn Bitcoin Through Blogging
5 PayPal Alternatives for Bloggers and Solopreneurs

Comment list

Comment add: Name：　Check：