title: How to find max value(not key) in an AVL tree?
body: <p>I build a simple AVL tree as following, each node has key and value. Now I want to implement a method that could return the key of node which has the largest value. For example, if I have a tree like:</p>
  
  <pre><code>               (7,1)
               /       \
          (4,3)       (13,8)
          /  \       /      \
      (2,4) (6,3) (11,8)      (15,2)
       / \   /      /  \      /     \
  (1,9)(3,0)(5,16)(9,2)(12,3)(14,3)(16,5)
                   / \
                (8,19)(10,4)
  </code></pre>
  
  <p>The method would return 8, as the node (8,19) has the largest value. Following is my avl tree and node constructor. I do try to implement this method by hand but somehow it doesn't work. I'd be grateful if someone coule help me.</p>
  
  <pre><code>public class AVLTreeImp&lt;T extends Comparable&lt;? super T&gt;,V&gt; implements AVLTree&lt;T,V&gt;{
      private Node&lt;T, V&gt; root;
      public class Node&lt;T extends Comparable&lt;? super T&gt;,V&gt; implements AVLTree.Node{
          T key;
          V value;
          Node&lt;T,V&gt; left;
          Node&lt;T,V&gt; right;
          Node&lt;T,V&gt; parent;
          int height;
          public Node(){
              this.key = null;
              this.left = null;
              this.right = null;
              this.parent = null;
              this.height = 0;
              this.value = null;
          }
          public Node(T key, V value, Node&lt;T,V&gt; left, Node&lt;T,V&gt; right){
              this.key = key;
              this.left = left;
              this.right = right;
              this.parent = null;
              this.height = 0;
              this.value = value;
          }
      }
  
      public AVLTreeImp(){
          this.root = null;
      }
  @Override
      public void insert(T key, V value){
          root = insert(root,key,value);
  
      }
      private Node&lt;T,V&gt; insert(Node&lt;T,V&gt; node, T key, V value){
          if (node == null){
              node = new Node&lt;T,V&gt;(key, value,null,null);
          }else{
              if (key.compareTo(node.key) &lt; 0){
                  node.left = insert(node.left, key, value);
                  if (!(isBalanced(node))) {
                      if (key.compareTo(node.left.key) &lt; 0) {
                          node = leftLeftRotation(node);
                      } else {
                          node = leftRightRotation(node);
                      }
                  }
              }else if (key.compareTo(node.key) &gt; 0){
                  node.right = insert(node.right,key,value);
                  if (!(isBalanced(node))){
                      if (key.compareTo(node.right.key) &gt; 0){
                          node = rightRightRotation(node);
                      }else{
                          node = rightLeftRotation(node);
                      }
                  }
              }
          }
          regenerateHeight(node);
          return node;
      }
  </code></pre>
  
  <hr>
  
  <p>Below is my implementation of this method, I'm not sure what's wrong with this.</p>
  
  <pre><code>public Integer findMax(){
          Node&lt;Integer,Integer&gt; result = (Node&lt;Integer,Integer&gt;)root;
          result.value = 0;
          return findMax((Node&lt;Integer, Integer&gt;) root,result);
      }
      private Integer findMax(Node&lt;Integer,Integer&gt; node,Node&lt;Integer,Integer&gt; result){
          if (node == null){
              return result.key;
          }
          if (node.value &gt; result.value || 
                  (node.value == result.value &amp;&amp; node.key.compareTo(result.key) &lt; 0)){
              result = node;
          }
          findMax(node.left,result);
          findMax(node.right,result);
          return result.key;
      }
  </code></pre>