C# LeetCode 112: Path Sum -(Easy)

Problem

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

Approach and Initial Thinking

We can think of this as a tree traversal with a running sum, where we start at the root with an initial sum = root.val.

For each node:

• We'll need to Add its value to the running sum.




• If it’s a leaf node, check if the running sum equals targetSum.

-Continue until either we find a path or exhaust the tree.

We can implement this with iterative DFS (Depth First Search) using a Stack.

We can make it performant by as soon as we meet all the following conditions we can stop the run, and return true:

• node.left == null


• node.right == null


• sum == targetSum

All conditions must be met in order for it to return true.

Code

public bool HasPathSum(TreeNode root, int targetSum)

{

    if (root == null) return false;



    var stack = new Stack<TreeNode>();

    var sumStack = new Stack<int>();



    stack.Push(root);

    sumStack.Push(root.val);



    while (stack.Count > 0)

    {

        var node = stack.Pop();

        var sum = sumStack.Pop();



        // Leaf check

        if (node.left == null && node.right == null && sum == targetSum)

            return true;



        if (node.right != null)

        {

            stack.Push(node.right);

            sumStack.Push(sum + node.right.val);

        }



        if (node.left != null)

        {

            stack.Push(node.left);

            sumStack.Push(sum + node.left.val);

        }

    }



    return false;

}

Note:

You could also use recursion (self-calling function) to complete this, but I believe my version is more readable, and a good learning point.

Please drop me a follow on twitter/x to hear about more articles in this series and other tech / developer tips.