Takefumi Yamamura's blog

This blog is for my memorandum.

Takefumi Yamamura's b!og

This blog is for my memorandum

Paths with Sum


You are given a binary tree in which each node contains an integer value(which might be positive or negative). Design an algorithm to count the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go down wards(traveling only from parent nodes to child nodes).

how to solve

solution1: brute force in recursively.

In the brute force approach, we just look at all possible paths. To do this, we traverse to each node. At each node, we recursively try all paths downwards, tracking the sum as we go. As soon as we hit our target sum, we increment the total.


solution2: using hash table.


Remove all ads