max subtree

max_subtree.py

class Node:

    def __init__(self):
        self.left_child = None
        self.right_child = None
        self.num = 0


def max_node(tree):
    return visit(tree)[1]


def visit(tree):
    left_sum = 0
    right_sum = 0
    max_sum = None
    max_subtree = None
    if tree.left_child is not None:
        left_sum, max_subtree = visit(tree.left_child)
        max_sum = left_sum

    if tree.right_child is not None:
        right_sum, max_right_subtree = visit(tree.right_child)
        if max_subtree is None or right_sum > max_sum:
            max_sum, max_subtree = right_sum, max_right_subtree

    total_sum = left_sum + right_sum + tree.num
    if max_subtree is None or total_sum >= max_sum:
        return total_sum, tree
    else:
        return total_sum, max_subtree


def read_tree():
    pass

if __name__ == '__main__':
    max_node(read_tree())