マツシタのお勉強

Print all paths which sum to a given value in a Binary Tree

Problem

You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum to a given value. The path dose not need to start or end at the root or leaf.

Solution

First, let’s approach this problem by using the Simplify approach.

Simplify Approach

What if the path had to start at the root, but could end anywhere? In this case, we can solve this problem easily by traversing from root node. By in-oder traversal, we add each node value to tmpSum. And when the tmpSum equals given sum, we print the path.

Generalize Solution

Well, What if the path can start from anywhere? In this case, this problem can be solved by checking from the deeper element.