PATH SUM: BINARY TREE

By: Saurav

2018-01-17 10:15:00 UTC

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.

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.

Return 0 / 1 ( 0 for false, 1 for true ) for this problem

InterviewBit

This problem is a variant of DFS where we are searching if the path from the root to leaf ends up with a given sum.

Base case would be if the root is null -> return 0 and if the root has no left and right child and its value is equal to the given sum -> return 1 (The check for left and right nil makes sure the search doesn't stop in the middle if the sum is met. We need the path to end at leaf node).

Otherwise, recursively check for the sum-root.data value on the left and right subtrees. At the end, if it's a leaf node and its value is equal to the net value, return true else return false. Let's see it in action:

def hasPathSum(a, b)
        return 0 if !a
        return 1 if (a.data == b) and !a.left and !a.right
        
        if ((a.left and hasPathSum(a.left, b-a.data) == 1) or 
            (a.right and hasPathSum(a.right, b-a.data) == 1))
            return 1
        else
            return 0
        end
       

    end

Looks good to me.


Let me know what you think!
twitter: sprakash24oct
linkedin

Owned & Maintained by Saurav Prakash

If you like what you see, you can help me cover server costs or buy me a cup of coffee though donation :)