BstArray.java

import java.util.Iterator;
import java.util.NoSuchElementException;

public class BstArray implements Iterable {

	private Comparable[] _tree;
	private int _size;

	public BstArray() {
		_tree = new Comparable[10];
		_size = 0;
	}

	public BstArray(Comparable[] list) {
		this();
		for (Comparable x : list)
			add(x);
	}

	public String toString() {
		String ans = "[";
		for (int i = 0; i < _tree.length; i++) {
			if (_tree[i] == null)
				ans += "_";
			else
				ans += _tree[i];
			if (i < _tree.length - 1)
				ans += ", ";
		}
		ans += "]";
		return ans;
	}

	// returns the index of val or -1 if not found
	public int find(Comparable val) {
		int i = 0;
		while (!_tree[i].equals(val))  {
			if (val.compareTo(_tree[i]) > 0)
				i = i * 2 + 2;
			else
				i = i * 2 + 1;
			if (i >= _tree.length || _tree[i] == null) {
				i = -1;
				break;
			}
		}
		return i;
	}

	public void add(Comparable r) {
		int index = 0;
		while (_tree[index] != null) {
			if (r.compareTo(_tree[index]) <= 0)
				index = index * 2 + 1;
			else
				index = index * 2 + 2;
			if (index >= _tree.length)
				resize();
		}
		_tree[index] = r;
		_size++;
	}

	private void resize() {
		Comparable[] newtree = new Comparable[_tree.length * 3];
		for (int i = 0; i < _tree.length; i++) 
			newtree[i] = _tree[i];
		_tree = newtree;
	}

	public void remove(Comparable x) {
		int i = find(x);
		if (i < 0)
			return;
		removeIndex(i);
		size--;
	}

	private void removeIndex(int i) {
		int left = 2 * i + 1, right = 2 * i + 2, j;
		if ((left  >= _tree.length || _tree[left]  == null) &&
		    (right >= _tree.length || _tree[right] == null)) {
			_tree[i] = null;
			return;
		}
		if (left < _tree.length && _tree[left] != null)
			j = left;
		else if (right < _tree.length && _tree[right] != null)
			j = right;
		else {
			j = left;
			while (true) {
				if (j * 2 + 2 < _tree.length && _tree[j * 2 + 2] != null)
					j = j * 2 + 2;
				else
					break;
			}
		}
		swap(i, j);
		removeIndex(j);
	}

	private void swap(int x, int y) {
		Comparable temp = _tree[x];
		_tree[x] = _tree[y];
		_tree[y] = temp;
	}

	public int size() {
		return _size;
	}

	public boolean isEmpty() {
		return _size == 0;
	}

	// longest root to leaf path
	public int height() {
		return height(0);
	}

	private int height(int i) {
		if (i >= _tree.length || _tree[i] == null)
			return 0;
		int left = height(2 * i + 1);
		int right = height(2 * i + 2);
		return 1 + Math.max(left, right);
	}

	// number of nodes without children
	public int countLeaves() {
		return countLeaves(0);
	}

	private int countLeaves(int i) {
		if (i >= _tree.length || _tree[i] == null)
			return 0;
		if ((2 * i + 1 >= _tree.length || _tree[2 * i + 1] == null) &&
		    (2 * i + 2 >= _tree.length || _tree[2 * i + 2] == null))
			return 1;
		return countLeaves(2 * i + 1) + countLeaves(2 * i + 2);
	}

	public boolean isALeaf(int pos) {
		int left  = 2 * pos + 1;
		int right = 2 * pos + 2;
		return pos   <  _tree.length && _tree[pos  ] != null  &&
		      (left  >= _tree.length || _tree[left ] == null) &&
		      (right >= _tree.length || _tree[right] == null);
	}

	// largest element in tree, or -1
	public int maxPos() {
		if (_size == 0)
			return -1;
		int ans = 0;
		while (true) {
			if (_tree[ans * 2 + 2] != null)
				ans = ans * 2 + 2;
			else
				break;
		}
		return ans;
	}

	// smallest element in tree, or -1
	public int minPos() {
		if (_size == 0)
			return -1;
		int ans = 0;
		while (true) {
			if (_tree[ans * 2 + 1] != null)
				ans = ans * 2 + 1;
			else
				break;
		}
		return ans;
	}

	// inorder: go left first, go down as far as possible, process node at bottom
	// (minimum element), then go right if possible, otherwise go up one level
	// and try to go right
	public void inorder() {
		inorder(0);
	}

	private void inorder(int r) {
		if (r >= _tree.length || _tree[r] == null)
			return;
		inorder(2 * r + 1);
		System.out.println(_tree[r]);
		inorder(2 * r + 2);
	}

	// preorder: process, go left, then go right - root processed first
	public void preorder() {
		preorder(0);
	}

	private void preorder(int r) {
		if (r >= _tree.length || _tree[r] == null)
			return;
		System.out.println(_tree[r]);
		preorder(2 * r + 1);
		preorder(2 * r + 2);
	}

	// postorder: go left, go right, then process - root processed last
	public void postorder() {
		postorder(0);
	}

	private void postorder(int r) {
		if (r >= _tree.length || _tree[r] == null)
			return;
		postorder(2 * r + 1);
		postorder(2 * r + 2);
		System.out.println(_tree[r]);
	}

	private class MyIterator implements Iterator {
		private int _index;
		private boolean _canRemove;

		public MyIterator() {
			_index = 0;
			_canRemove = false;
		}

		public Comparable next() {
			if (_index >= _tree.length || _tree[_index] == null) {
				_canRemove = false;
				throw new NoSuchElementException();
			}
			_canRemove = true;
			return _tree[_index];
		}

		public boolean hasNext() {
			return _index < _tree.length && _tree[_index] != null;
		}

		public void remove() {
			if (_canRemove)
				removeIndex(_index);
			_canRemove = false;
		}

	}

	public Iterator iterator() {
		return new MyIterator();
	}

	public static void main(String[] args) {
		Comparable[] list =  {4, 8, 7, 12, 1, 3, 9};
		BstArray bst = new BstArray(list);
		System.out.println(bst);
	}
}

TreeNode.java

public class TreeNode<T> {

	T _value;
	TreeNode _left, _right;

	public TreeNode(T value, TreeNode<T> left, TreeNode<T> right) {
		_value = value;
		_left = left;
		_right = right;
	}

	public TreeNode(T value) {
		this(value, null, null);
	}

	public T getValue() {
		return _value;
	}

	public TreeNode<T> getLeft() {
		return _left;
	}

	public TreeNode<T> getRight() {
		return _right;
	}

	public void setValue(T value) {
		_value = value;
	}

	public void setLeft(TreeNode left) {
		_left = left;
	}

	public void setRight(TreeNode right) {
		_right = right;
	}
}