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?

• vnp: left in problem statement looks like a typo. Shouldn't it be leaf?
• John Lane: Nope, I don't see a typo.
• Gerrit0: " 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.
• John Lane: I am sorry @vnp you are right. I will fix it.

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

• John Lane: Does this consider larger trees?
• aghast: 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.
• John Lane: This looks great. Just tried it out. Any idea what the time complexity is?
• maxb: 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.