data_structures.binary_tree.binary_tree_maximum_path_sum

Attributes

tree

Classes

GetMaxPathSum	GetMaxPathSum takes root node of a tree as initial argument.
TreeNode

Functions

construct_tree(→ TreeNode)

The below tree

Module Contents

class data_structures.binary_tree.binary_tree_maximum_path_sum.GetMaxPathSum(root: TreeNode)

GetMaxPathSum takes root node of a tree as initial argument. Upon calling max_path_sum(), it returns maximum path sum from the tree.

# Test

The below tree looks like this

10

/

5 -3

/

3 2 11

/

3 -2 1

Result will be calculated like : 3 -> 3 -> 5 -> 10 -> -3 -> 11 As it is the maximum path possible.

>>> root = TreeNode(10)
>>> root.left = TreeNode(5)
>>> root.right = TreeNode(-3)
>>> root.left.left = TreeNode(3)
>>> root.left.right = TreeNode(2)
>>> root.right.right = TreeNode(11)
>>> root.left.left.left = TreeNode(3)
>>> root.left.left.right = TreeNode(-2)
>>> root.left.right.right = TreeNode(1)

>>> GetMaxPathSum(root).max_path_sum()
29

max_path_sum() → int

Driver method to get max_path_sum by calling traverse method. :return max_path_sum:

traverse(root: TreeNode | None) → int

Returns maximum path sum by recursively taking max_path_sum from left and max_path_sum from right if current Node has a left or right Node.

Parameters:

root (root -> tree)

Return int:

root

sum = -9999999999

class data_structures.binary_tree.binary_tree_maximum_path_sum.TreeNode

left: TreeNode | None = None

right: TreeNode | None = None

val: int

data_structures.binary_tree.binary_tree_maximum_path_sum.construct_tree() → TreeNode

The below tree

-10 /

9 20

/

15 7

>>> root = TreeNode(-10)
>>> root.left = TreeNode(9)
>>> root.right = TreeNode(20)
>>> root.right.left = TreeNode(15)
>>> root.right.right = TreeNode(7)

>>> GetMaxPathSum(construct_tree()).max_path_sum()
42

data_structures.binary_tree.binary_tree_maximum_path_sum.tree