Binary Tree Path Sum
BINARY TREE
RECURSION
DEPTH-FIRST SEARCH

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.

Examples:

hasPathSum([0,1,2,3,4,5], 5) // true // There is a path from root to leaf with sum 5 (0->1->4)

hasPathSum([1,2,3], 5) // false // There is no path from root to leaf with sum 5.

Time Complexity

The time complexity of this problem is O(n), where n is the number of nodes in the binary tree. This is because we need to visit each node of the tree exactly once.

Loading...