Given a binary search tree and a value k, please find a node in the binary search tree whose value is closest to k.

ClosestBSTNode.java

//Method 1:

public Node getClosestBSTNode( Node root, int k ){
  if( root == null ){
    return null;
  }
  return getClosestBSTNode( root, k, root.data() - k );
}

public Node getClosestBSTNode( Node node, int k, int parentDiff ){
  if( parentDiff == 0 ){
    return node;
  }
  Node closestLeftBSTNode  = getClosestBSTNode( node.getLeft(), k, node.getData() - k );
  Node closestRightBSTNode = getClosestBSTNode( node.getRight(), k, node.getData() - k );
  
  if( parentDiff < ( closestLeftBSTNode.getData() - k) || parentDiff < ( closestRightBSTNode.getData() - k) ){
    return node;
  }
  if( Math.abs (closestLeftBSTNode.getData() - k) <= Math.abs( closestRightBSTNode.getData() - k ) ){
    return closestLeftBSTNode;
  } else{
    return closestRightBSTNode;
  }
}

// Method 2:

public Node getClosestBSTNode( Node root ){
  return getClosestBSTNode( root, k );
}

public Node getClosestBSTNode( Node node, int k, Node closestNode ){
  if ( node == null ){
    return null;
  }
  
  int currData = node.data
  if( currData == k ){
    return node;
  } else if( currData < k ){
    int diff = Math.abs( currData - k );
    int closestDiff = Math.abs( closestNode.getData() - k );
    if( diff < closestDiff ){
      if( node.getRight() != null ){
        return getClosestBSTNode( node.getRight(), k, node );
      } else{
        return closestNode;
      }
    } else{
      if( node.getRight() != null ){
        return getClosestBSTNode( node.getRight(), k, closestNode );
      } else{
        return closestNode;
      }
    }
  } else if ( currData > k ){
    int diff = Math.abs( currData - k );
    int closestDiff = Math.abs( closestNode.getData() - k );
    if( diff < closestDiff ){
      if( node.getLeft() != null ){
        return getClosestBSTNode( node.getLeft(), k, node );
      } else{
        return closestNode;
      }
    } else{
      if( node.getLeft() != null ){
        return getClosestBSTNode( node.getLeft(), k, closestNode );
      } else{
        return closestNode;
      }
    }
  }
}