CODEWITHSUNDEEP
javarecursionbinary-search-tree
Danny Randolph
Danny Randolph

Reputation: 35

Java BST searching for max value, most efficiently

Long time reader first time poster (mostly because 99% of all questions have already been answered on here!!!)

I've been browsing for about an hour and I am unable to find a solution to this problem. Given a pre-sorted balanced binary search tree, I am tasked with making the following method to find the max value in the tree more efficient:

private int max(IntTreeNode root) {
    if (root.left == null && root.right == null)
        return root.data;
    else {
        int maxValue = root.data;
        if (root.left != null)
            maxValue=Math.max(maxValue,max(root.left));
        if (root.right != null)
            maxValue = Math.max(maxValue,max(root.right));
        return maxValue;

Here are my 2 thoughts (and likely one of them is wrong and that's the problem):

1) While it is sorted and balanced, it can vary in size, therefore I have to check each and every leaf, because the only parameter to the method is a root I don't see any shortcut there.

2) Same cause, single parameter, means I have to use the line maxValue=Math.max(maxValue,max(root.left)); in each recursive call in order to keep a running number on maxValue. So I don't see where to skip any of those useless calculations.

The question being asked, is how would you make the method more efficient given the sorted balanced BST information, the other information is just where I am on it all. Thanks

edit I guess I was worried about an 11 element tree

         1
       /   \
      2      3
     / \    /  \
    4  5    6    7
   / \/ \  /  \ / \  (making a tree got real hard)
  8  9 10 11        (this row is a little messed up but demonstrates the point)

Point being if you only take the right, you will end up at 7, and thus be wrong. Unless I'm confused on the meaning of sorted BST, do BST's always have to be full on the bottom row?

Upvotes: 1

Views: 13916

Answers (2)

Khalid Abu El-Soud
Khalid Abu El-Soud

Reputation: 119

for the LHS it always less than the root so no need to search for you can use this one :

private int max(IntTreeNode root) {
     if ( root.right == null) // no need to search in LHS
       return root.data;
     else {
        int maxValue = root.data;
        maxValue = Math.max(maxValue,max(root.right));
     }
     return maxValue;

if this is not you want asked me again what are you want is your expected output from this method and I'll try to help you :)

Upvotes: 0

4J41
4J41

Reputation: 5095

In a BST the right most element is the maximum.

Here is the pseudocode.

int getMax(Node root) { //check if root is null
   if(root.right == null) {
       return root.data 
   } else {
       return getMax(root.right)
   }
}

For a balanced tree, order would be O(log n).

Upvotes: 2

Related Questions