public class NoneEmptyBSTree implements Table {
    String key;
    Integer data;
    Table left, right;
    
    
	
	
	public NoneEmptyBSTree(String key, Integer data, Table left, Table right) {
		super();
		this.key = key;
		this.data = data;
		this.left = left;
		this.right = right;
	}

	@Override
	public Integer get(String k) {
		if (k.equals(key)) {
			return data;
		} else if (k.compareTo(key) < 0) {
			return left.get(k);
		} else {
			return right.get(k);
		}
	}

	@Override
	public Table put(String k, Integer v) {
		if (k.equals(key)) {
			return new NoneEmptyBSTree(k,v,left,right);
		} else if (k.compareTo(key) < 0) {
			return new NoneEmptyBSTree(key,data,left.put(k, v),right);
		} else {
			return new NoneEmptyBSTree(key,data,left,right.put(k, v));
		}
	}

	@Override
	public String show() {
		
		return left.show() + key + ":" + data + "\n" + right.show();
	}

}