sol.py

from tree import Node
import random


class TreeNode(Node):
    def __init__(self, val=None):
        super().__init__(data=val)

    def insert_node(self, val):
        if self.left is None and self.right is not None:
            self.left = TreeNode(val)
        elif self.right is None and self.left is not None:
            self.right = TreeNode(val)
        elif self.left is None and self.right is None:
            choice = random.choice(['LEFT', 'RIGHT'])
            if choice=='LEFT':
                self.left = TreeNode(val)
            else:
                self.right = TreeNode(val)
        elif self.left is not None and self.right is not None:
            choice = random.choice(['LEFT', 'RIGHT'])
            if choice=='LEFT':
                self.left.insert_node(val)
            else:
                self.right.insert_node(val)


def max_path_sum_util(root, res):
    if root is None:
        return 0
    if root.left is None and root.right is None:
        return root.data
    l_sum = max_path_sum_util(root.left, res)
    r_sum = max_path_sum_util(root.right, res)
    if root.left is not None and root.right is not None:
        res[0] = max(res[0], l_sum + r_sum + root.data)
        return max(l_sum, r_sum) + root.data
    elif root.left is not None and root.right is None:
        return l_sum + root.data
    elif root.left is None and root.right is not None:
        return r_sum + root.data


def maxPathSum(root):
    res = [-10**10]
    max_path_sum_util(root, res)
    return res[0]


if __name__=='__main__':
    tree = TreeNode(50)
    for _ in range(5):
        val = random.randint(-50, 50)
        tree.insert_node(val)
    tree.prettyPrint(); print('\n\n')
    print(maxPathSum(tree))