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 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:

/* Check if the left child of root HAS NO CHILDREN and check if the right child of root HAS NO CHILDREN. We check if a node is a leaf node by checking if it is null on both its right child and its left child. */ if ((root->left == NULL) && (root->right == NULL)) {

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.

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

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