Grokking Tree Coding Patterns for Interviews

0% completed

​

Solution: Binary Tree Path Sum

Problem Statement

Given a root of the binary tree and an integer S, return true if the tree has a path from root-to-leaf such that the sum of all the node values of that path equals S. Otherwise, return false.

Examples

Example 1:

  • Input: root = [1, 2, 3, 4, 5, 6, 7], S = 10
  • Expected Output: true
  • Justification: The tree has 1 -> 3 -> 6 root-to-leaf path having sum equal to 10.

Example 2:

  • Input: root = [12, 7, 1, 9, null, 10, 5], S = 23
  • Expected Output: true
  • Justification: The tree has `12 -> 1 -> 10

.....

.....

.....

Like the course? Get enrolled and start learning!
N

Nafis Molla

· 4 years ago

how does the or work in the return statement? Are they both run simultaneously?

Show 2 replies
L

lejafilip

· 2 years ago

static bool hasPath(TreeNode *root, int sum) {
    if(!root)
      return false;
  
    std::stack<std::pair<TreeNode*, int>> nodes;
    nodes.push({root, sum - root->val});

    while(!nodes.empty())
    {
      auto node = nodes.top();
      nodes.pop();

      if(node.second == 0 && !node.first->left && !node.first->right)
      {
        return true;
      }

      if(node.first->left)
        nodes.push({node.first->left, node.second - node.first->left->val});
      
      if(node.first->right)
        nodes.push({node.first->right, node.second - node.first->right->val});
    }

    return false;
  }