Posted on Aug 6

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