Max Sum of Nodes in Each Path in Binary Tree

Question

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 = [0] 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[0]: curr_max[0] = 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[0] # 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?

Answer 1

It seems like you are doing a little too much work.

The maximum sum of a node that is None will be 0.

The maximum sum of a node that is not None will be the value of the node, plus the max of the sums of the two children.

That recursion alone should be enough to avoid using intermediate data structures. Something like:

def find_max_sum_of_binary_tree_path(root): if root is None: return 0 left_sum = find_max_sum_of_binary_tree_path(root.left) right_sum = find_max_sum_of_binary_tree_path(root.right) return root.value + max((left_sum, right_sum))