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,

 5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1

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.

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

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 25 26

class Solution { public: bool hasPathSum(TreeNode* root, int sum) { if (root == NULL) { return false; } queue< pair > q; q.push(make_pair(root, sum)); // we have to add up to sum while (!q.empty()) { auto p = q.front(); // get front element from the queue q.pop(); if (p.first->left != NULL) { // pushes left q.push(make_pair(p.first->left, p.second - p.first->val)); } if (p.first->right != NULL) { // pushes right q.push(make_pair(p.first->right, p.second - p.first->val)); } 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. } };