Forgetting null/base-case handling
Wrong move: Recursive traversal assumes children always exist.
Usually fails on: Leaf nodes throw errors or create wrong depth/path values.
Fix: Handle null/base cases before recursive transitions.
Build confidence with an intuition-first walkthrough focused on tree fundamentals.
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.
Example 1:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 Output: true Explanation: The root-to-leaf path with the target sum is shown.
Example 2:
Input: root = [1,2,3], targetSum = 5 Output: false Explanation: There are two root-to-leaf paths in the tree: (1 --> 2): The sum is 3. (1 --> 3): The sum is 4. There is no root-to-leaf path with sum = 5.
Example 3:
Input: root = [], targetSum = 0 Output: false Explanation: Since the tree is empty, there are no root-to-leaf paths.
Constraints:
[0, 5000].-1000 <= Node.val <= 1000-1000 <= targetSum <= 1000Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Tree
[5,4,8,11,null,13,4,7,2,null,null,null,1] 22
[1,2,3] 5
[] 0
path-sum-ii)binary-tree-maximum-path-sum)sum-root-to-leaf-numbers)path-sum-iii)path-sum-iv)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #112: Path Sum
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
return dfs(root, targetSum);
}
private boolean dfs(TreeNode root, int s) {
if (root == null) {
return false;
}
s -= root.val;
if (root.left == null && root.right == null && s == 0) {
return true;
}
return dfs(root.left, s) || dfs(root.right, s);
}
}
// Accepted solution for LeetCode #112: Path Sum
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func hasPathSum(root *TreeNode, targetSum int) bool {
var dfs func(*TreeNode, int) bool
dfs = func(root *TreeNode, s int) bool {
if root == nil {
return false
}
s += root.Val
if root.Left == nil && root.Right == nil && s == targetSum {
return true
}
return dfs(root.Left, s) || dfs(root.Right, s)
}
return dfs(root, 0)
}
# Accepted solution for LeetCode #112: Path Sum
# 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
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
def dfs(root, s):
if root is None:
return False
s += root.val
if root.left is None and root.right is None and s == targetSum:
return True
return dfs(root.left, s) or dfs(root.right, s)
return dfs(root, 0)
// Accepted solution for LeetCode #112: Path Sum
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
pub fn has_path_sum(root: Option<Rc<RefCell<TreeNode>>>, target_sum: i32) -> bool {
match root {
None => false,
Some(node) => {
let mut node = node.borrow_mut();
// 确定叶结点身份
if node.left.is_none() && node.right.is_none() {
return target_sum - node.val == 0;
}
let val = node.val;
Self::has_path_sum(node.left.take(), target_sum - val)
|| Self::has_path_sum(node.right.take(), target_sum - val)
}
}
}
}
// Accepted solution for LeetCode #112: Path Sum
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
if (root === null) {
return false;
}
const { val, left, right } = root;
if (left === null && right === null) {
return targetSum - val === 0;
}
return hasPathSum(left, targetSum - val) || hasPathSum(right, targetSum - val);
}
Use this to step through a reusable interview workflow for this problem.
BFS with a queue visits every node exactly once — O(n) time. The queue may hold an entire level of the tree, which for a complete binary tree is up to n/2 nodes = O(n) space. This is optimal in time but costly in space for wide trees.
Every node is visited exactly once, giving O(n) time. Space depends on tree shape: O(h) for recursive DFS (stack depth = height h), or O(w) for BFS (queue width = widest level). For balanced trees h = log n; for skewed trees h = n.
Review these before coding to avoid predictable interview regressions.
Wrong move: Recursive traversal assumes children always exist.
Usually fails on: Leaf nodes throw errors or create wrong depth/path values.
Fix: Handle null/base cases before recursive transitions.