I wanted to get a review on an algorithm I wrote for a binary tree problem. The problem is the following.
Return the maximum sum between all branches in a binary tree. A branch is defined as all paths from root to leaf.
class Node(object): def __init__(self, value): self.value = value self.left = None self.right = None #branch one root = Node(10) second = Node(5) root.left = second third = Node(1) second.left = third fourth = Node(3) third.left = fourth tenth = Node(5) third.right = tenth fifth = Node(20) root.right = fifth sixth = Node(60) fifth.left = sixth seventh = Node(3) fifth.right = seventh nineth = Node(40) seventh.right = nineth def find_max_sum_of_binary_tree_path(root): curr_list =  curr_max =  def binary_tree_recurse(node): if node: if not node.left and not node.right: curr_list.append(node.value) list_sum = sum(curr_list) if list_sum > curr_max: curr_max = list_sum curr_list.pop() curr_list.append(node.value) binary_tree_recurse(node.left) binary_tree_recurse(node.right) curr_list.pop() binary_tree_recurse(root) return curr_max # 10 # / \ # 5 20 # / / \ # 1 60 3 # / \ \ # 3 5 40 find_max_sum_of_binary_tree_path(root) #should return 90 based on my tree >90
I'd like to stick to a recursive approach, but open to suggestions on anything else. I am mostly concerned about time complexity and improving the performance of this function. Does anyone know what the current time complexity is?