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:
                list_sum = sum(curr_list)
                if list_sum > curr_max[0]:
                    curr_max[0] = list_sum


    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

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?

  • \$\begingroup\$ left in problem statement looks like a typo. Shouldn't it be leaf? \$\endgroup\$
    – vnp
    Commented Mar 14, 2018 at 0:28
  • \$\begingroup\$ Nope, I don't see a typo. \$\endgroup\$
    – John Lane
    Commented Mar 14, 2018 at 0:40
  • \$\begingroup\$ " 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. \$\endgroup\$
    – Gerrit0
    Commented Mar 14, 2018 at 0:42
  • \$\begingroup\$ I am sorry @vnp you are right. I will fix it. \$\endgroup\$
    – John Lane
    Commented Mar 14, 2018 at 1:08

1 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))
  • \$\begingroup\$ Does this consider larger trees? \$\endgroup\$
    – John Lane
    Commented Mar 14, 2018 at 1:13
  • \$\begingroup\$ 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. \$\endgroup\$
    – aghast
    Commented Mar 14, 2018 at 1:19
  • \$\begingroup\$ This looks great. Just tried it out. Any idea what the time complexity is? \$\endgroup\$
    – John Lane
    Commented Mar 14, 2018 at 3:07
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – maxb
    Commented Mar 14, 2018 at 11:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.