class Solution {
  /**
   * Given a Binary Search Tree and an Integer, returns the Entry in this tree
   * with the smallest key that is strictly larger than k.
   *
   * @param tree
   *     Binary search tree to search in.
   * @param k
   *     The key of the resulting entry should be strictly larger than this k.
   * @return The entry with smallest key, strictly larger than k.
   */
  static Entry higherEntry(BinarySearchTree tree, int k) {
    if(tree == null){
      return null;
    }
    if(tree.getKey() <= k){
      if(tree.hasRight()){
        return higherEntry(tree.getRight(), k);
      }
      return null;
    }
    if (tree.getKey() > k){
      Entry closest = tree.getEntry();
      if(tree.hasLeft()){
        Entry leftEntry = higherEntry(tree.getLeft(), k);
        if(leftEntry == null){
          return closest;
        } else {
          return leftEntry;
        }
      }
    }
    return tree.getEntry();
  }
}