C# LeetCode 112: Path Sum -(Easy)

#tutorial #programming #csharp #leetcode

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;
}