public class SearchTree{
	
	   class TreePosition{
			Object element;
			int key;
			TreePosition parent;
			TreePosition leftChild;
			TreePosition rightChild;
			
			public Object element(){
				return this.element;
			}
			
			public TreePosition(Object o, int k){
				this.element = o;
				this.key = k;
				this.leftChild = null;
				this.rightChild = null;
				this.parent = null;
			}
		}
	   
	   TreePosition root;
	
		public SearchTree(){
			/* 
			 *  Ein Blatt ist ein Knoten (TreePosition) fuer den gilt
			 *  element = null
			 *  key = 0
			 *  leftChild = null
			 *  rightChild = null
			 *  
			 *  Beim Initialisieren ist die Wurzel somit ein Blatt
			 *  und enthaelt keine Daten.
			 *  Daten werden nur in inneren Knoten gespeichert.
			 */ 
			root = new TreePosition(null,0);			
		}	

		public void insertItem(Object o, int k){
			/*
			 * So implementieren, dass ein Suchbaum entsteht bei dem 
			 * die inneren Knoten Daten/Key enthalten.  
			 */
		}
		

		public Object findElement(int key){
			/*
			 *  Gib das Element mit Schluessel k zurueck, falls
			 *  dieses nicht existiert null zurueckgeben.
			 */
			return null;		
		}
		
		
		public String reportAllKeys(int left, int right){
			/*
			 *  Gib einen String zurueck, der alle keys k
			 *  (aufsteigend sortiert, jeweils mit Leerzeichen 
			 *  getrennt) mit left<=k und k<=right enthaelt. 
			 *  Sie koennen davon ausgehen, dass jeder key nur 
			 *  einmal auftritt und left<=right gilt.
			 */ 
			String result = new String();
			return result;
		}
}