Given a tree and a sum , return true if there is a path from the root down to a leaf , such that adding up all the values along the path equals the given sum . Strategy : subtract the node value from the sum when recurring down , and check to see if the sum is 0 when you run out of tree .
public virtual bool haspathSum ( Node node , int sum ) { if ( node == null ) { return ( sum == 0 ) ; } else { bool ans = false ; int subsum = sum - node . data ; if ( subsum == 0 && node . left == null && node . right == null ) { return true ; } if ( node . left != null ) { ans = ans || haspathSum ( node . left , subsum ) ; } if ( node . right != null ) { ans = ans || haspathSum ( node . right , subsum ) ; } return ans ; } }