What is the best algorithm to get maximum total value in binary tree?

Question

I have some questions about getting maximum sum value in binary tree.

Each node can have two child nodes (Left, Right)

Sum[7, 3, 8, 7, 5] is the maximum sum value for the example above.

First, I thought choosing each max child node is best answer, but it is not.

triangle = [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]
depth = 0
total = []

N = triangle[0][0]

def min_max(depth, N, total):
    if (depth+1) == len(triangle):
        return total
    else:
        a,b = triangle[depth+1][triangle[depth].index(N)], triangle[depth+1][triangle[depth].index(N)+1]
        total.append(max(a,b))
        N = max(a,b)
        return min_max(depth+1, N, total)

min_max(depth, N, total) # [8, 1, 7, 5]

Then, I thought getting all cases sum and comparing, but it seems to worsen the time complexity.

What is the proper algorithm for this task?

What output do you want?

Sharim09
– Sharim09

2022-06-07 04:38:32 +00:00
Commented Jun 7, 2022 at 4:38 — Sharim09
– Sharim09, Commented Jun 7, 2022 at 4:38
@SharimIqbal In case, [7, 3, 8, 7, 5] is the answer.

jtoyhh
– jtoyhh

2022-06-07 04:45:31 +00:00
Commented Jun 7, 2022 at 4:45 — jtoyhh
– jtoyhh, Commented Jun 7, 2022 at 4:45

Abhinav Mathur · Accepted Answer · 2022-06-07 05:27:38Z

1

I'm not entirely sure what the issue is; a simple, recursive way to calculate the sum for a node's children should be enough.

def get_max(node):
    if not node:
        return 0
    return node.value + max(get_max(node.left), get_max(node.right))

Each node is visited only once, so this will have a complexity of O(number of nodes) = O(N)

answered Jun 7, 2022 at 5:27

Abhinav Mathur

8,2363 gold badges14 silver badges26 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Ryan Zhang · Accepted Answer · 2022-06-07 04:45:52Z

I'm guessing you want the maximum sum of a path from the root of the tree to any child. With a minimax algorithm, you can acheive a time complexity of roughly O(2^N), where N is the depth of the tree.

However, I have here an O(N^2) dynamic programming solution to your problem, where N is the depth of the tree, and therefore O(N^2) is the scale of the number of nodes in the tree.

Define dp[i] to be the maximum sum of a path from the root of the tree to node i. Your base case is dp[root] = value of the root node. Iterate through the nodes from top to bottom (so root to child), and the dp function is

dp[node] = value_of_node[node]+max(dp[top_left_of[node]], dp[top_right_of[node]]);

Hopefully this is intuitive: the maximum sum of a path to a certain node has to come from either its top left or top right node.

Your answer is the maximum of all the dp values of the children of the tree.

Ausrada404 · Accepted Answer · 2022-06-07 14:15:37Z

This question is equal to finding a path that has the maximum sum. The path must start from the root and end with a leaf node.

If the input is the root node of the binary tree, the answer is easy to figure out.

class Node:
    def __init__(self, val: int, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def max_sum_path(root: Node) -> int:
    """

    :param root: Node
    :return: the max path sum
    """
    if not root:
        return 0
    return root.val + max(max_sum_path(root.left), max_sum_path(root.right))

If the input is the triangle(list). we can build the tree first.


# create node from each element
triangle = [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]
triangle_nodes = []
for level_val_lst in triangle:
    node_lst = [Node(e) for e in level_val_lst]
    triangle_nodes.append(node_lst)

# create tree
levels = len(triangle)
for level in range(levels - 1):
    node_lst = triangle_nodes[level]
    next_node_lst = triangle_nodes[level + 1]
    cnt_nodes = len(node_lst)
    for i, node in enumerate(node_lst):
        left_index = i
        right_index = i + 1
        node.left = next_node_lst[left_index]
        node.right = next_node_lst[right_index]
root = triangle_nodes[0][0]

res = max_sum_path(root)
print(res)

score 0 · Accepted Answer · 2022-06-07 19:23:10Z

0

The triangle in the OP's post is a DAG (directed acyclic graph) while the recursive solution (posted by Abhinav Mathur) traverses it like a BT (binary tree) of the same height. So for the recursive solution to be O(N), N must be the number of nodes in the BT, not in the DAG. If N instead is the height of the BT (same as the DAG), the complexity becomes O(2^N) (as stated by Ryan Chang).

Since the triangle is a DAG, I suppose it is possible to reformulate the problem as Finding the Longest Path in a DAG (with the numbers in the triangle thought of as distances). It has linear complexity in the number of vertices and edges, O(V+E). That probably is the best one can do with this problem.

edited Jun 7, 2022 at 19:23

answered Jun 7, 2022 at 8:51

user18978409

Collectives™ on Stack Overflow

What is the best algorithm to get maximum total value in binary tree?

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related