//GOBruen

class FindNext
{
	int data;
	FindNext left;
	FindNext right;

	FindNext(int d)
	{
		data = d;
		left = null;
		right = null;
	}

	FindNext()
	{
		data = 0;
		left = null;
		right = null;
	}

	public void insert(int d)
	{
		if(d < data)
		{
			if(left == null)
			{
				left = new FindNext(d);
			}
			else
			{
				left.insert(d);
			}					

		}
		else if(d > data)
		{
			if(right == null)
			{
				right = new FindNext(d);
			}
			else
			{
				right.insert(d);
			}

		}

	}

	public static int getNext(FindNext tree, int num){
		int retNum;

		retNum = tree.searchTree(num, 0, 0);
		if(retNum == 0){
			return num;
		}else{
			return retNum;
		}		
	}

/*
	searchTree() uses a small finite state machine to determine
	if the right value has been found.
*/

	public int searchTree(int num, int nextNum, int state){
		switch(state){
			case 0:
				if(data > num){
				nextNum = data;
				state = 1;
				}
				if(right != null)
					nextNum = right.searchTree(num, nextNum, state);
				if(left != null)
					nextNum = left.searchTree(num, nextNum, state);
				break;
			case 1:
				if((data > num)&&(nextNum > data)){
				nextNum = data;
				}
				if(right != null)
					nextNum = right.searchTree(num, nextNum, state);
				if(left != null)
					nextNum = left.searchTree(num, nextNum, state);
				break;
			default:
			break;
		}

	return nextNum;
	}

	public static void main(String args[]){

		System.out.println("Start");
		FindNext tree = new FindNext();
		tree.insert(4);
		tree.insert(2);
		tree.insert(1);
		tree.insert(3);
		tree.insert(6);
		tree.insert(5);
		tree.insert(9);
		//tree.displayTree(0);
		int foundNum;
		foundNum = getNext(tree, 5);
		System.out.println("Found number: "+foundNum);
	
	}


}