old_contents: # Time:  O(n)
  # Space: O(logn)
  #
  # Given a binary tree and a sum, determine if the tree has a root-to-leaf path 
  # such that adding up all the values along the path equals the given sum.
  # 
  # For example:
  # Given the below binary tree and sum = 22,
  #               5
  #              / \
  #             4   8
  #            /   / \
  #           11  13  4
  #          /  \      \
  #         7    2      1
  # return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
  #
  
  # Definition for a  binary tree node
  class TreeNode:
      def __init__(self, x):
          self.val = x
          self.left = None
          self.right = None
      
  class Solution:
      # @param root, a tree node
      # @param sum, an integer
      # @return a boolean
      def hasPathSum(self, root, sum):
          if root is None:
              return False
          
          if root.left is None and root.right is None and root.val == sum:
              return True
          
          return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)
      
  if __name__ == "__main__":
      root = TreeNode(5)
      root.left = TreeNode(4)
      root.right = TreeNode(8)
      root.left.left = TreeNode(11)
      root.left.left.right = TreeNode(2)
      print Solution().hasPathSum(root, 22)
new_contents: # Time:  O(n)
  # Space: O(h), h is height of binary tree
  #
  # Given a binary tree and a sum, determine if the tree has a root-to-leaf path 
  # such that adding up all the values along the path equals the given sum.
  # 
  # For example:
  # Given the below binary tree and sum = 22,
  #               5
  #              / \
  #             4   8
  #            /   / \
  #           11  13  4
  #          /  \      \
  #         7    2      1
  # return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
  #
  
  # Definition for a  binary tree node
  class TreeNode:
      def __init__(self, x):
          self.val = x
          self.left = None
          self.right = None
      
  class Solution:
      # @param root, a tree node
      # @param sum, an integer
      # @return a boolean
      def hasPathSum(self, root, sum):
          if root is None:
              return False
          
          if root.left is None and root.right is None and root.val == sum:
              return True
          
          return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)
      
  if __name__ == "__main__":
      root = TreeNode(5)
      root.left = TreeNode(4)
      root.right = TreeNode(8)
      root.left.left = TreeNode(11)
      root.left.left.right = TreeNode(2)
      print Solution().hasPathSum(root, 22)
  
subject: Update path-sum.py