data_structures.binary_tree.maximum_sum_bst

Attributes

INT_MAX
INT_MIN

Classes

TreeNode

Functions

max_sum_bst(→ int)

The solution traverses a binary tree to find the maximum sum of

Module Contents

class data_structures.binary_tree.maximum_sum_bst.TreeNode

left: TreeNode | None = None

right: TreeNode | None = None

val: int = 0

data_structures.binary_tree.maximum_sum_bst.max_sum_bst(root: TreeNode | None) → int

The solution traverses a binary tree to find the maximum sum of keys in any subtree that is a Binary Search Tree (BST). It uses recursion to validate BST properties and calculates sums, returning the highest sum found among all valid BST subtrees.

>>> t1 = TreeNode(4)
>>> t1.left = TreeNode(3)
>>> t1.left.left = TreeNode(1)
>>> t1.left.right = TreeNode(2)
>>> print(max_sum_bst(t1))
2
>>> t2 = TreeNode(-4)
>>> t2.left = TreeNode(-2)
>>> t2.right = TreeNode(-5)
>>> print(max_sum_bst(t2))
0
>>> t3 = TreeNode(1)
>>> t3.left = TreeNode(4)
>>> t3.left.left = TreeNode(2)
>>> t3.left.right = TreeNode(4)
>>> t3.right = TreeNode(3)
>>> t3.right.left = TreeNode(2)
>>> t3.right.right = TreeNode(5)
>>> t3.right.right.left = TreeNode(4)
>>> t3.right.right.right = TreeNode(6)
>>> print(max_sum_bst(t3))
20

data_structures.binary_tree.maximum_sum_bst.INT_MAX = 9223372036854775806

data_structures.binary_tree.maximum_sum_bst.INT_MIN = -9223372036854775806