Path Sum

Problem Statement

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.

What to notice first

• Only root-to-leaf paths count; intermediate paths do not.
• A leaf is defined as having no left and right children.
• Subtract current value from targetSum as you traverse down.

Examples

Input	targetSum	Output	Path
[5,4,8,11,null,13,4,7,2,null,1]	22	true	5→4→11→2
[1,2,3]	5	false	No path sums to 5

Constraints

• The number of nodes is in the range [0, 5000].
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

Real-World Applications

Where this pattern appears

• File system hierarchies and directory structures
• DOM tree manipulation in web browsers
• XML/JSON parsing and configuration management
• Organizational hierarchies and permission trees

Complexity Comparison

Approach	Time	Space	Best When
DFS Recursive	O(n)	O(h)	Simple, clean code; h is height
BFS Iterative	O(n)	O(w)	Avoid recursion; w is max width

Approach 1: DFS Recursive

★ Recommended

Use depth-first search. At each node, subtract its value from targetSum. Check if leaf and sum equals zero.

⏱ Time O(n) Visit each node once 💾 Space O(h) Recursion stack depth

Pseudocode

function hasPathSum(root, targetSum):
    if not root: return false

    if not root.left and not root.right:
        return root.val == targetSum

    remaining = targetSum - root.val
    return hasPathSum(root.left, remaining) or hasPathSum(root.right, remaining)

Solution Code

Python

path_sum_dfs_recursive.py

from typing import Optional


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def hasPathSum(root: Optional[TreeNode], targetSum: int) -> bool:
    """
    Check if tree has root-to-leaf path summing to targetSum using recursive DFS.
    Time: O(n), Space: O(h) for recursion stack
    """
    if not root:
        return False

    # Leaf node check
    if not root.left and not root.right:
        return root.val == targetSum

    # Subtract current value and check left and right subtrees
    remaining = targetSum - root.val
    return hasPathSum(root.left, remaining) or hasPathSum(root.right, remaining)


# Test cases
if __name__ == "__main__":
    # Example 1: [5,4,8,11,null,13,4,7,2,null,1], targetSum = 22
    root = TreeNode(5)
    root.left = TreeNode(4)
    root.left.left = TreeNode(11)
    root.left.left.left = TreeNode(7)
    root.left.left.right = TreeNode(2)
    root.right = TreeNode(8)
    root.right.left = TreeNode(13)
    root.right.right = TreeNode(4)
    root.right.right.right = TreeNode(1)

    print(hasPathSum(root, 22))  # True
    print(hasPathSum(root, 20))  # False

    # Example 2: Single node
    single = TreeNode(1)
    print(hasPathSum(single, 1))  # True
    print(hasPathSum(single, 2))  # False

C++

path_sum_dfs_recursive.cpp

#include <iostream>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        /**
         * Check if tree has root-to-leaf path summing to targetSum using recursive DFS.
         * Time: O(n), Space: O(h) for recursion stack
         */
        if (!root) return false;

        // Leaf node check
        if (!root->left && !root->right) {
            return root->val == targetSum;
        }

        // Subtract current value and check left and right subtrees
        int remaining = targetSum - root->val;
        return hasPathSum(root->left, remaining) || hasPathSum(root->right, remaining);
    }
};

// Test cases
int main() {
    // Example 1: [5,4,8,11,null,13,4,7,2,null,1], targetSum = 22
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(4);
    root->left->left = new TreeNode(11);
    root->left->left->left = new TreeNode(7);
    root->left->left->right = new TreeNode(2);
    root->right = new TreeNode(8);
    root->right->left = new TreeNode(13);
    root->right->right = new TreeNode(4);
    root->right->right->right = new TreeNode(1);

    Solution sol;
    cout << boolalpha;
    cout << "Example 1 (target 22): " << sol.hasPathSum(root, 22) << endl;  // true
    cout << "Example 1 (target 20): " << sol.hasPathSum(root, 20) << endl;  // false

    return 0;
}

Java

PathSumDFSRecursive.java

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}
    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    /**
     * Check if tree has root-to-leaf path summing to targetSum using recursive DFS.
     * Time: O(n), Space: O(h) for recursion stack
     */
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;

        // Leaf node check
        if (root.left == null && root.right == null) {
            return root.val == targetSum;
        }

        // Subtract current value and check left and right subtrees
        int remaining = targetSum - root.val;
        return hasPathSum(root.left, remaining) || hasPathSum(root.right, remaining);
    }
}

class Main {
    public static void main(String[] args) {
        // Example 1: [5,4,8,11,null,13,4,7,2,null,1], targetSum = 22
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.left.left = new TreeNode(11);
        root.left.left.left = new TreeNode(7);
        root.left.left.right = new TreeNode(2);
        root.right = new TreeNode(8);
        root.right.left = new TreeNode(13);
        root.right.right = new TreeNode(4);
        root.right.right.right = new TreeNode(1);

        Solution sol = new Solution();
        System.out.println("Example 1 (target 22): " + sol.hasPathSum(root, 22));  // true
        System.out.println("Example 1 (target 20): " + sol.hasPathSum(root, 20));  // false
    }
}

JavaScript

path_sum_dfs_recursive.js

/**
 * Definition for a binary tree node.
 */
class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

/**
 * Check if tree has root-to-leaf path summing to targetSum using recursive DFS.
 * Time: O(n), Space: O(h) for recursion stack
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {boolean}
 */
function hasPathSum(root, targetSum) {
    if (!root) return false;

    // Leaf node check
    if (!root.left && !root.right) {
        return root.val === targetSum;
    }

    // Subtract current value and check left and right subtrees
    const remaining = targetSum - root.val;
    return hasPathSum(root.left, remaining) || hasPathSum(root.right, remaining);
}

// Test cases
const root = new TreeNode(5);
root.left = new TreeNode(4);
root.left.left = new TreeNode(11);
root.left.left.left = new TreeNode(7);
root.left.left.right = new TreeNode(2);
root.right = new TreeNode(8);
root.right.left = new TreeNode(13);
root.right.right = new TreeNode(4);
root.right.right.right = new TreeNode(1);

console.log("Example 1 (target 22):", hasPathSum(root, 22));  // true
console.log("Example 1 (target 20):", hasPathSum(root, 20));  // false

Rust

path_sum_dfs_recursive.rs

use std::cell::RefCell;
use std::rc::Rc;

#[derive(Debug)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

/**
 * Check if tree has root-to-leaf path summing to targetSum using recursive DFS.
 * Time: O(n), Space: O(h) for recursion stack
 */
pub fn has_path_sum(root: Option<Rc<RefCell<TreeNode>>>, target_sum: i32) -> bool {
    match root {
        None => false,
        Some(node) => {
            let node_ref = node.borrow();
            let val = node_ref.val;
            let left = node_ref.left.clone();
            let right = node_ref.right.clone();
            drop(node_ref);

            // Leaf node check
            if left.is_none() && right.is_none() {
                return val == target_sum;
            }

            // Subtract current value and check left and right subtrees
            let remaining = target_sum - val;
            has_path_sum(left, remaining) || has_path_sum(right, remaining)
        }
    }
}

fn main() {
    println!("Example 1: Path sum check with DFS");
}

Go

path_sum_dfs_recursive.go

package main

import "fmt"

/**
 * Definition for a binary tree node.
 */
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

/**
 * Check if tree has root-to-leaf path summing to targetSum using recursive DFS.
 * Time: O(n), Space: O(h) for recursion stack
 */
func hasPathSum(root *TreeNode, targetSum int) bool {
    if root == nil {
        return false
    }

    // Leaf node check
    if root.Left == nil && root.Right == nil {
        return root.Val == targetSum
    }

    // Subtract current value and check left and right subtrees
    remaining := targetSum - root.Val
    return hasPathSum(root.Left, remaining) || hasPathSum(root.Right, remaining)
}

func main() {
    fmt.Println("Example 1: Path sum check with DFS")
}

Approach 2: BFS Iterative

alternative

Use a queue to track (node, current_sum) pairs. Process nodes level-by-level; check leaf when dequeued.

⏱ Time O(n) Visit each node once 💾 Space O(w) Queue size (max level width)

Pseudocode

function hasPathSum(root, targetSum):
    if not root: return false

    queue = [(root, root.val)]

    while queue:
        node, currentSum = queue.pop()

        if not node.left and not node.right and currentSum == targetSum:
            return true

        if node.left:
            queue.push((node.left, currentSum + node.left.val))
        if node.right:
            queue.push((node.right, currentSum + node.right.val))

    return false

Solution Code

Python

path_sum_bfs_iterative.py

from typing import Optional
from collections import deque


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def hasPathSum(root: Optional[TreeNode], targetSum: int) -> bool:
    """
    Check if tree has root-to-leaf path summing to targetSum using iterative BFS.
    Uses queue to store (node, current_sum) pairs.
    Time: O(n), Space: O(w) where w is max width
    """
    if not root:
        return False

    queue = deque([(root, root.val)])

    while queue:
        node, current_sum = queue.popleft()

        # Check leaf node
        if not node.left and not node.right and current_sum == targetSum:
            return True

        if node.left:
            queue.append((node.left, current_sum + node.left.val))
        if node.right:
            queue.append((node.right, current_sum + node.right.val))

    return False


# Test cases
if __name__ == "__main__":
    # Example 1: [5,4,8,11,null,13,4,7,2,null,1], targetSum = 22
    root = TreeNode(5)
    root.left = TreeNode(4)
    root.left.left = TreeNode(11)
    root.left.left.left = TreeNode(7)
    root.left.left.right = TreeNode(2)
    root.right = TreeNode(8)
    root.right.left = TreeNode(13)
    root.right.right = TreeNode(4)
    root.right.right.right = TreeNode(1)

    print(hasPathSum(root, 22))  # True
    print(hasPathSum(root, 20))  # False

    # Example 2: Single node
    single = TreeNode(1)
    print(hasPathSum(single, 1))  # True
    print(hasPathSum(single, 2))  # False

C++

path_sum_bfs_iterative.cpp

#include <iostream>
#include <queue>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        /**
         * Check if tree has root-to-leaf path summing to targetSum using iterative BFS.
         * Queue stores (node, current_sum) pairs.
         * Time: O(n), Space: O(w) where w is max width
         */
        if (!root) return false;

        queue<pair<TreeNode*, int>> q;
        q.push({root, root->val});

        while (!q.empty()) {
            auto [node, current_sum] = q.front();
            q.pop();

            // Check leaf node
            if (!node->left && !node->right && current_sum == targetSum) {
                return true;
            }

            if (node->left) {
                q.push({node->left, current_sum + node->left->val});
            }
            if (node->right) {
                q.push({node->right, current_sum + node->right->val});
            }
        }

        return false;
    }
};

// Test cases
int main() {
    // Example 1: [5,4,8,11,null,13,4,7,2,null,1], targetSum = 22
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(4);
    root->left->left = new TreeNode(11);
    root->left->left->left = new TreeNode(7);
    root->left->left->right = new TreeNode(2);
    root->right = new TreeNode(8);
    root->right->left = new TreeNode(13);
    root->right->right = new TreeNode(4);
    root->right->right->right = new TreeNode(1);

    Solution sol;
    cout << boolalpha;
    cout << "Example 1 (target 22): " << sol.hasPathSum(root, 22) << endl;  // true
    cout << "Example 1 (target 20): " << sol.hasPathSum(root, 20) << endl;  // false

    return 0;
}

Java

PathSumBFSIterative.java

import java.util.*;

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;

        Queue<TreeNode> nodeQueue = new LinkedList<>();
        Queue<Integer> sumQueue = new LinkedList<>();
        nodeQueue.offer(root);
        sumQueue.offer(root.val);

        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.poll();
            int sum = sumQueue.poll();

            if (node.left == null && node.right == null && sum == targetSum) {
                return true;
            }

            if (node.left != null) {
                nodeQueue.offer(node.left);
                sumQueue.offer(sum + node.left.val);
            }

            if (node.right != null) {
                nodeQueue.offer(node.right);
                sumQueue.offer(sum + node.right.val);
            }
        }

        return false;
    }
}

System.out.println("PathSum Solution");

JavaScript

path_sum_bfs_iterative.js

/**
 * Definition for a binary tree node.
 */
class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

/**
 * Check if tree has root-to-leaf path summing to targetSum using iterative BFS.
 * Queue stores [node, current_sum] pairs.
 * Time: O(n), Space: O(w) where w is max width
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {boolean}
 */
function hasPathSum(root, targetSum) {
    if (!root) return false;

    const queue = [[root, root.val]];

    while (queue.length > 0) {
        const [node, currentSum] = queue.shift();

        // Check leaf node
        if (!node.left && !node.right && currentSum === targetSum) {
            return true;
        }

        if (node.left) {
            queue.push([node.left, currentSum + node.left.val]);
        }
        if (node.right) {
            queue.push([node.right, currentSum + node.right.val]);
        }
    }

    return false;
}

// Test cases
const root = new TreeNode(5);
root.left = new TreeNode(4);
root.left.left = new TreeNode(11);
root.left.left.left = new TreeNode(7);
root.left.left.right = new TreeNode(2);
root.right = new TreeNode(8);
root.right.left = new TreeNode(13);
root.right.right = new TreeNode(4);
root.right.right.right = new TreeNode(1);

console.log("Example 1 (target 22):", hasPathSum(root, 22));  // true
console.log("Example 1 (target 20):", hasPathSum(root, 20));  // false

Rust

path_sum_bfs_iterative.rs

use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;

#[derive(Debug)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

/**
 * Check if tree has root-to-leaf path summing to targetSum using iterative BFS.
 * Queue stores (node, current_sum) pairs.
 * Time: O(n), Space: O(w) where w is max width
 */
pub fn has_path_sum(root: Option<Rc<RefCell<TreeNode>>>, target_sum: i32) -> bool {
    if root.is_none() {
        return false;
    }

    let mut queue = VecDeque::new();
    queue.push_back((root.clone().unwrap(), root.unwrap().borrow().val));

    while !queue.is_empty() {
        let (node, current_sum) = queue.pop_front().unwrap();
        let node_ref = node.borrow();

        // Check leaf node
        if node_ref.left.is_none() && node_ref.right.is_none() && current_sum == target_sum {
            return true;
        }

        if let Some(left) = node_ref.left.clone() {
            queue.push_back((left.clone(), current_sum + left.borrow().val));
        }
        if let Some(right) = node_ref.right.clone() {
            queue.push_back((right.clone(), current_sum + right.borrow().val));
        }
    }

    false
}

fn main() {
    println!("Example 1: Path sum check with BFS");
}

Go

path_sum_bfs_iterative.go

package main

import "fmt"

/**
 * Definition for a binary tree node.
 */
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

/**
 * Pair struct to hold node and sum
 */
type Pair struct {
    node      *TreeNode
    sum       int
}

/**
 * Check if tree has root-to-leaf path summing to targetSum using iterative BFS.
 * Queue stores (node, current_sum) pairs.
 * Time: O(n), Space: O(w) where w is max width
 */
func hasPathSum(root *TreeNode, targetSum int) bool {
    if root == nil {
        return false
    }

    queue := []Pair{{node: root, sum: root.Val}}

    for len(queue) > 0 {
        pair := queue[0]
        queue = queue[1:]

        node := pair.node
        currentSum := pair.sum

        // Check leaf node
        if node.Left == nil && node.Right == nil && currentSum == targetSum {
            return true
        }

        if node.Left != nil {
            queue = append(queue, Pair{node: node.Left, sum: currentSum + node.Left.Val})
        }
        if node.Right != nil {
            queue = append(queue, Pair{node: node.Right, sum: currentSum + node.Right.Val})
        }
    }

    return false
}

func main() {
    fmt.Println("Example 1: Path sum check with BFS")
}

Related Problems

• Minimum Depth of Binary Tree ↗ Easy #111
• Path Sum II ↗ Medium #113
• Sum Root to Leaf Numbers ↗ Medium #129

Interview Tips

Key trade-offs to discuss

• DFS vs BFS: DFS is more natural for paths; BFS is more natural for levels.
• Early termination: Both can return true immediately upon finding a valid path.
• Space: DFS uses O(h) for recursion; BFS uses O(w) for queue.
• Edge cases: Empty root, single node, all negative/positive values.

← Previous
#108 Convert Sorted Array to Binary Search Tree Next
#114 Flatten Binary Tree to Linked List →