# Max Sum of Nodes in Each Path in Binary Tree

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?

• left in problem statement looks like a typo. Shouldn't it be leaf? – vnp Mar 14 at 0:28
• Nope, I don't see a typo. – John Lane Mar 14 at 0:40
• " A branch is defined as all paths from root to left." <-- I believe this is what vnp is referring to, I believe it should be leaf as well. – Gerrit0 Mar 14 at 0:42
• I am sorry @vnp you are right. I will fix it. – John Lane Mar 14 at 1:08

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))

• Does this consider larger trees? – John Lane Mar 14 at 1:13
• Yes. A large tree is just a node joining two smaller trees. Once you find the maxsum of each smaller tree, finding the answer for the larger tree is shown. – Austin Hastings Mar 14 at 1:19
• This looks great. Just tried it out. Any idea what the time complexity is? – John Lane Mar 14 at 3:07
• Since the function find_max_sum_of_binary_tree_path only runs a single time for each node, and it runs in approximately the same time for each node, the execution time is O(n), where n is the number of nodes. – maxb Mar 14 at 11:11