Path Sum for Binary Tree Using C++ (LeetCode Programming) Given a binary tree an
ID: 3912805 • Letter: P
Question
Path Sum for Binary Tree Using C++ (LeetCode Programming)
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example:
Given the below binary tree and sum = 22,
return true, as there exists a root-to-leaf path 5-4-11-2 which sum is 22.
Please explain the source code for the recursion solution and the iterative solution. Include comments to the source codes. I have added my own a comments to the recursion source code. However, you still need to add more comments to help me to understand the parts of the code I don't understand, specifically the harder to read and harder to follow iterative source code.
RECURSION
Recursively, if we visit a leaf node, we check the remaining sum with the value of the node. We subtract the value of nodes from the intended sum and carry them recursively down along the leaf nodes from the root.
This recursion is a DFS (Depth First Search) meaning that it may be quicker to find a route. For example, if the first route satisfies, the program will exit very soon without exploring the full search tree.
ITERATIVE
The BFS (Breadth First Search) uses a queue data structure to store the current parent node. Every iteration, the queue pops out a front node and pushes back its children, this eventually gives a level-by-level traversal. It means, that it is likely for the BFS to explore full every possible nodes in the search tree.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
/** * 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: bool hasPathSum(TreeNode* root, int sum) { if (root == NULL) { return false; } /* Check if the left child of root HAS NO CHILDREN and check if the right child of root HAS NO CHILDREN.*/
if ((root->left == NULL) && (root->right == NULL)) { // if it is a leaf node, we compare the remaining sum with the root value return sum == root->val; } // subtract the node value and continue recursively visiting two sub trees. return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val); } };
Explanation / Answer
here is the explanation as the form of comment in code : ---------------->>>>>>>>>>>>
/**
* 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:
bool hasPathSum(TreeNode* root, int sum) {
//checking for the empty tree
if (root == NULL) {
return false;
}
//checking the root has left child and right child
if ((root->left == NULL) && (root->right == NULL)) {
// if it is a leaf node, we compare the remaining sum with the root value
return sum == root->val;
}
// subtract the node value and continue recursively visiting two sub trees.
//here we are checking for both left and right child so we can find the sum
return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
}
};
class Solution {
public:
/*in this iterative solution we are pushing the a pair of TreeNode pointer and the remaining sum so far
in a queue and processing the treenode by its level means(DFS) first we explore the root level
than second level all nodes and so on
for this we have to store the remaining sum so we are doing this by pairing it and pushing it into queue
*/
bool hasPathSum(TreeNode* root, int sum) {
//same checking for empty TreeNode
if (root == NULL) {
return false;
}
queue< pair > q;
//here we put the root and and the sum given as argument to the pair queue
q.push(make_pair(root, sum)); // we have to add up to sum
while (!q.empty()) {//checking for empty queue
auto p = q.front(); // get front element from the queue
q.pop();//popping out the pair to process it
//checking for left children if it is there we will push onto the queue for further processing
if (p.first->left != NULL) { // pushes left
//here we are making pair of left child of current node which is being processed
//and the (current node sum value stored as a pair) - (current node value)
//and pushing it onto the queue
q.push(make_pair(p.first->left, p.second - p.first->val));
}
//checking for right children if it is there we will push onto the queue for further processing
if (p.first->right != NULL) { // pushes right
//here we are making pair of right child of current node which is being processed
//and the (current node sum value stored as a pair) - (current node value)
//and pushing it onto the queue
q.push(make_pair(p.first->right, p.second - p.first->val));
}
//if there is no children of current node means it is a leaf node
//then we will check that (current node sum value is equal to its value or not)
//if it is equal we are done we find the sum path
if ((p.first->left == NULL) && (p.first->right == NULL)) {
if (p.second == p.first->val) { // if it is a leaf node and the sum adds up.
return true;
}
}
}
return false; // finish the tree, but no routes found.
}
};