⚠️ This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#112) before relying on it.

🌳 Path Sum

An interactive visualization of DFS on a binary tree to find a root-to-leaf path with a target sum. Watch the running sum update as the algorithm explores each path.

DFS LeetCode 112 ↗ Easy

The 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.

Interactive Visualization

Tree (level-order, use "null" for gaps)

Target Sum

Preset

Speed:

Binary Tree

Press Step or Play to begin.

Code

fun hasPathSum(root: TreeNode?, targetSum: Int): Boolean {    if (root == null) {        return false    }    val remaining = targetSum - root.`val`    if (root.left == null && root.right == null) {        return remaining == 0    }    return hasPathSum(root.left, remaining) ||           hasPathSum(root.right, remaining) }

def hasPathSum(root, targetSum):    if not root:        return False    targetSum -= root.val    if not root.left and not root.right:        return targetSum == 0    return (hasPathSum(root.left, targetSum) or            hasPathSum(root.right, targetSum))

Current Step

Press Step or Play to begin.

How It Works

Key Insight

Instead of tracking a running sum, subtract each node's value from targetSum as you traverse down the tree. When you reach a leaf node, simply check whether the remaining targetSum equals zero. This avoids passing an accumulator through the recursion.

The Algorithm

Base case (null node): If the current node is null, return False — there is no path here.
Subtract: Reduce targetSum by the current node's value.
Leaf check: If the node has no left or right child, it is a leaf. Return whether targetSum == 0.
Recurse: Otherwise, recurse on the left subtree and the right subtree. If either returns True, a valid path exists.

Complexity

Time O(n)

Space O(h)

We visit every node at most once, giving O(n) time where n is the number of nodes. The recursion stack uses O(h) space where h is the height of the tree — O(log n) for a balanced tree and O(n) in the worst case (a skewed tree).