Path Sum for Binary Tree Using C++ (LeetCode Programming) Given a binary tree an
ID: 3912148 • 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 exist 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. For example, you can add comments to the following piece of code:
Can you remind me why we have an arrow -> between root and left. What does the arrow represent in C++? Does the arrow have a special technical name in C++?
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; } if ((root->left == NULL) && (root->right == NULL)) { // if it is a leaf node, we compare the remaining sum with the value return sum == root->val; } // subtract the node value and continue visit two sub trees. return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val); } };
Explanation / Answer
Recursive solution:
1)A function haspathsum(root,sum) is defined where root=>root of tree and sum=>sum to be found along a path .
2) A recursion is used to solve problem so,base condition is return back when we encounter a leaf node which is checked using following code
if((root->left==NULL)&&(root->right==NULL)) then it is a leaf node.At each leaf node we also check if remaining sum is equal to leaf node value
if found true then solution found.
3)if current node is not a leaf node:
then look for solution in left subtree or right subtree by decreasing value of sum by current node's value
hasPathSum(root->left, sum - root->val) ||
hasPathSum(root->right, sum - root->val);
note:if solution found on any of the subtree then overall solution is true as boolean OR(||)is used between both function call.
root->left:=>means we are accessing a member of structure through their pointer
iterative solution:
An empty queue(Q(pair(root,sum)) created
1)Keep traversing tree level by level from level one till last level.
2)making a pair of(root,sum)for each node.
3)Jush push root to the queue Q,if it has left node then make pair(root->left,sum-root->data)and push in queue Q.
4)check for right node if found, then make a pair(root->right,sum-root->data) and push in Queue Q.
5)keep doing 3 and 4 until last level arrived.
6)At,Last level check if any node value is equal to remaining sum in pair(root,sum)
if true then solution found;
7)if queue Q is empty and no solution found then no solution.
for further Query please comment;