public class BST implements Iterable<Integer> {
	
	// Attribute:
	private Integer content; 	// Inhalt
	private BST right; 			// rechtes Kind
	private BST left; 			// linkes Kind
	private BST parent; 		// Elternknoten
	
	// Konstruktor:
	public BST(Integer content, BST left, BST right, BST parent) { 
		this.content = content;
		this.left = left;
		this.right = right;
		this.parent = parent;
	}
	
	// Fügt eine Zahl an (nicht gefordert)
	public void insert(Integer x) {
		if (x < content) {
			if (left == null)
				left = new BST(x, null, null, this);
			else
				left.insert(x);
		} else {
			if (right == null)
				right = new BST(x, null, null, this);
			else
				right.insert(x);
		}
	}
	
	
	// Methode, die den Iterator zurückgibt
	public TreeTerator iterator() {
		return new TreeTerator(this);
	}
	

	// Iterator als innere Klasse des Suchbaums, über den iteriert wird
	public class TreeTerator implements java.util.Iterator<Integer> {
		
		private BST current; // aktuelle Position des Iterators
		
		public TreeTerator(BST bst) {
			current = bst;
			while (current.left != null) // hat linken Nachfolger
				current = current.left;
		}
		
		public boolean hasNext() {
			if (current != null) // current entspricht next!!! einfach Variable zu next umbenennen falls dann klarer.
				return true;     // current speichert immer das nächste (noch nicht über hasNext zurückgegebene) Element
			return false;
		}
		
		public Integer next() {
			if (!hasNext())
				throw new java.util.NoSuchElementException();
			
			Integer elem = current.content;
			
			if (current.right != null) {
				current = current.right;
				while (current.left != null) // hat linken Nachfolger
					current = current.left;
			} else {
				BST child = null;
				while (current != null && current.right == child) {
					child = current;
					current = current.parent;
				}
			}
			
			return elem;
		}
		
	}
	
	
	// Test (Baum aus der Angabe WS 2017/18):
	public static void main(String[] args) {
		BST wurzel = new BST(11, null, null, null);

		wurzel.insert(5);
		wurzel.insert(2);
		wurzel.insert(9);
		wurzel.insert(1);
		wurzel.insert(4);
		wurzel.insert(3);
		wurzel.insert(18);
		wurzel.insert(20);
		wurzel.insert(21);
		wurzel.insert(19);
		
		for (Integer x : wurzel) {
			System.out.println("Element: " + x);
		}
	}
}