title: Java BST searching for max value, most efficiently
body: <p>Long time reader first time poster (mostly because 99% of all questions have already been answered on here!!!)</p>
  
  <p>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:</p>
  
  <pre class="lang-java prettyprint-override"><code>private int max(IntTreeNode root) {
      if (root.left == null &amp;&amp; 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;
  </code></pre>
  
  <p>Here are my 2 thoughts (and likely one of them is wrong and that's the problem):</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>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</p>
  
  <p><strong>edit</strong>
  I guess I was worried about an 11 element tree</p>
  
  <pre><code>         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)
  </code></pre>
  
  <p>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?</p>