Path Sum In Binary Tree

Given a binary tree and a sum. Write a method to check if there's a path from a root to a leaf where a sum of nodes equals to the given sum.

Note: A leaf is a node without children

Example 1

Input:        1    sum = 15
             / \
            2   3
           /   /
          4   5  
             /  
            6 

Output: true

Explanation: path 1->3->5->6

Example 2

Input:     1   sum = 3
          / \  
         5   3 

Output: false

Algorithm

The idea is to make a traversal while passing the sum and reduce the sum by a node value.

• return true if sum equals zero at a leaf node
• return false if the sum not equals zero at a leaf node

Let's check the idea step by step. Assume we have a tree and the sum (see below)

 

 

During the tree traversal, we reduce the sum on a node value. The result will look like this.

 

 

At a leaf node, we check the resulting sum:

• return true if sum equals zero at a leaf node
• return false if the sum not equals zero at a leaf node

Try to answer the question. Will the algorithm work if a tree contains negative values?

Code

    public bool HasPathSum(TreeNode root, int sum)
    {
        if (root == null)
        {
            return false;
        }

        sum -= root.Value;
        if (root.Left == null && root.Right == null)
        {
            return sum == 0;
        }

        return HasPathSum(root.Left, sum) || HasPathSum(root.Right, sum);
    }

Time Complexity: O(n)