CODEWITHSUNDEEP
tree
Vishesh Aggarwal
Vishesh Aggarwal

Reputation: 113

Maximum Sum BST in a Binary Tree

Given a binary tree root, the task is to 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 sub-tree of a node contains only nodes with keys less than the node's key.
- The right sub-tree of a node contains only nodes with keys greater than the node's key.
- Both the left and right sub-trees must also be binary search trees.

I have tried to solve this by going on every node and checking is it BST or not and then finding its sum.
But my approach is getting TLE. What should be the optimized approach for solving this question?

Upvotes: 4

Views: 660

Answers (1)

alGOds
alGOds

Reputation: 159

The time complexity of your approach is O(n^2).

You can try checking whether a subtree is a BST while calculating the sum of all elements in that subtree. So that would require just one traversal of the given tree, reducing the complexity to O(n).

A post-order traversal should work.

If you feel stuck while implementing such an approach, this might help : https://www.youtube.com/watch?v=Zz7R9I9j2kI

Upvotes: 4

Related Questions