CODEWITHSUNDEEP
algorithmbinary-treebinary-search-tree
CupOfGreenTea
CupOfGreenTea

Reputation: 409

Maximum sum of BST-subtree in a non-BST binary tree

For the below binary tree the problem statement says the maximum sum of a BST-subtree in the binary tree is 20 (rooted at 3), but why not include the root node as well (with value of 1) to obtain an even larger sum of 21?

Thanks in advance.

     1
    / \
   /   \
  4      3
 / \    / \
2   4   2  5
          / \
         4   6

Upvotes: 1

Views: 134

Answers (2)

Stef
Stef

Reputation: 15505

A possibility is that the definition of "subtree" requires that when you include a node in the subtree, you must include all of its descendants with it. This would mean that a subtree is entirely characterized by its subroot.

Upvotes: -2

Elliott
Elliott

Reputation: 2623

Any node in a tree T, together with all the nodes below it, comprise a subtree of T.
(http://subtree.askdefine.com/)

So if you include the root node then you need to include its descendants to the left as well as the right. As @user2357112 pointed out, this would mean that the subtree wouldn't be a BST.

Upvotes: 0

Related Questions