Determine if Binary Tree Contains a Path with Given Sum

Given a binary tree and a target value, determine if there exists a root-to-leaf path that sums up to the given target.

This problem can be solved by applying depth-first traversal and processing each level recursively in a pre-order manner. This means that at each level, we want to subtract the node value from the target value of the current level. If the difference is 0, and the current node has no children, then the current path is one of the possible root-to-leaf paths that sum up to the target. Otherwise, continue to the next node and repeat the process.

const hasSumPath = (root, tgt) => {
  if (!root)
    return false;

  if (tgt - root.val === 0 && !root.left && !root.right)
    return true;

  return hasSumPath(root.left, tgt - root.val)
    || hasSumPath(root.right, tgt - root.val);
}

The time complexity for this problem depends on the shape of the tree. If the tree is relatively balanced, then the time complexity is close to O(log(n)). If the tree is extremely skewed, then the time complexity is closer to O(n).