find the maximum sum of all sub-trees in a binary search tree

Back>

In order to find the maximum sum of all sub-tree in a binary search tree, we need to get all the sums of a tree. In order to get the sum of a tree, we need to use post order.

BTree.java

BTreePrinter.java

GlobalOptimumOne.java

GlobalOptimumOneTest.java

The time complexity is O(N) since we need to visit each node. There is little extra space used, the space complexity is O(1).

The above problem is to find a global optimum in a tree. Other similar problems include:

• find the minimum sum of all sub-trees in a binary search tree
• find the maximum sum of path in a binary search tree
• find the size of a tree
• find the height of a tree
• find the longest path in a tree
• find the lowest cost path from node A to node B
• find the closest common parent for node A and node B
• find the smallest subtree that contains both node A and node B
• find the distance between node A and node B

Let's solve another example problem.

find the maximum sum of path in a binary search tree.

a path can have any node as start or end nodes 

for example the following tree has max path sum 35 

10 

/ \ 

5 20

the following tree has max path sum 30 

10 

/ \ 

-5 20

The key here is to example the path sum of left leaf and right leaf, only include those leaf with positive path sum.

BTree.java

BTreePrinter.java

GlobalOptimumTwo.java

GlobalOptimumTwoTest.java

The time complexity is O(N) since we also need to visit all the nodes. There is little extra space used, the space complexity is O(1).

Let's take a look at a third example.
find the closest common parent for node A and node B

BTree.java

BTreePrinter.java

GlobalOptimumThree.java

GlobalOptimumThreeTest.java

here if we can assume node A and node B is in the tree, otherwise, we need to double check that when we found the common parent. The time complexity is O(N) and the space complexity is O(1).