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
  • 1
    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

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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