private Node put(Node x, int key, int val) {
        if (x == null)
            return new Node(key,val);
        if (key < x.key) {
            x.left = put(x.left, key, val);
        } else if (key > x.key) {
            x.right = put(x.right, key, val);
        } else {
            x.val = val;
        }
        return x;
    }