November Challenge
Problem
Given the root node of a binary search tree, return the sum of values of all nodes with a value in the range [low, high].
It simply calculate the sum for those between the given high and low value.
Solution I
This is a binary search tree, which means that the right child will be larger than the root, and the left child will be smaller.
However, It is also quite simple to run through all those Nodes by either BFS or DFS.
Let’s give BFS a try, and see the outcome. Append the root’s child to the list, que,if there is one, and pop out from que as recursive. Whenever the value of the root is between high and low, we add it to the ans.
This way should be fast for programmer since we don’t have to decide which Node we are not going to visit. But it should be slow for the program.
As we expected, it is slow.
You can utilize the properties of binary search tree, and it should be faster.
