Skip to main content
Code Review

Return to Question

edited body
Source Link
John Lane
John Lane
  • 51
  • 3

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 leftleaf.

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?

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 left.

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?

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?

Source Link
John Lane
John Lane
  • 51
  • 3

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 left.

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?