Problem
Given a binary tree root
, return the maximum sum of all keys of any sub-tree which is also a Binary Search Tree (BST).
Assume a BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- Both the left and right subtrees must also be binary search trees.
Examples
Example 1
|
|
Example 2
|
|
Example 3
|
|
Constraints
- The number of nodes in the tree is in the range
[1, 4 * 10^4]
. -4 * 10^4 <= Node.val <= 4 * 10^4
Solution
Method 1 – Postorder Traversal with State Tracking
Intuition
To find the maximum sum BST in a binary tree, we need to check every subtree to see if it is a BST and calculate its sum. By traversing the tree in postorder, we can gather information from the left and right subtrees before making decisions at the current node.
Approach
- Use postorder traversal to visit each node after its children.
- For each node, collect:
- Whether its left and right subtrees are BSTs.
- The minimum and maximum values in its subtrees.
- The sum of its subtree if it is a BST.
- If the current node forms a BST with its children, update the global maximum sum.
- If not a BST, propagate invalid state upwards.
- Return the maximum sum found.
Code
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Complexity
- ⏰ Time complexity:
O(n)
, since each node is visited once. - 🧺 Space complexity:
O(h)
, whereh
is the height of the tree due to recursion stack.