Check if binary tree has path sum

Learn how to create an algorithm to check if binary tree has path sum.

Example

Given a binary tree and a number check if there is a path in a binary tree from root to leaf (leaf is a node with no children) such that adding their sum equals to that number. If yes then return true else return false.

Input:
[5,4,8,11,null,13,4,7,2,null,null,null,1]
22

Output:
true

You can see the path sum in this image.

Finding binary tree sum path with recursion

• We use a tracker to check if the sum was present in the tree. It will be false by default.
• Start from 0 and pass the current sum to the child node by calling the function recursively with left and right childs.
• In each call if the sum is equal to the number and the current node is a leaf node that is does not have any child then mark true in the tracker.
• At the end return the tracker value.

const hasPathSum = (root, sum) => {
    //Tracker
    const tracker = { 'b' : false};
    
    //Traverse the tree
    //Start with 0 and keep adding to it
    traverse(root, 0, sum, tracker);
    
    return tracker['b'];
};

const traverse = (root, sum, match, found) => {
    //If no root then return
    if(!root){
        return;
    }
    
    //Add the value with current sum
    sum += root.val;
    
    //If sum is present and is leaf node then mark true
    if(sum === match && !root.left && !root.right){
        found['b'] = true;
    }
    
    //Traverse the left and right child nodes
    traverse(root.left, sum, match, found);
    traverse(root.right, sum, match, found);
}

Input:
//Assume that this input array will be converted to tree.
hasPathSum([5,4,8,11,null,13,4,7,2,null,null,null,1], 22)

Output:
true

Time complexity: O(n) where n is all the nodes in the tree.
Space complexity: O(n) where n is all the nodes in the tree (considering the call stack).