//GOBruen
//ProveNull.java

/*
*
*	In order to prove that a binary tree has one more
* null pointer than it has nodes, we must obtain the number of
* null pointers and the number of nodes then compare those numbers.
*
* This program creates a simple binary tree with limited functions 
*
* findNullPointers() accepts the initial value 0 and traverses the tree
* until it reaches dead ends or null pointers. When null pointers are
* found, the count increments. When the last nulls are reached the final count
* is returned
*
* findNodes() accepts the initial value of 1 because there is atleast the root node
* in the tree. The tree is traversed and the count is incremented each time a 
* node is visited. When all the nodes have been visited and the null pointers reached,
* the count is returned.
*/



public class ProveNull
{
	int value;
	ProveNull left;
	ProveNull right;

	ProveNull(int v)
	{
		value = v;
		left = null;
		right = null;
	}

	ProveNull()
	{
		left = null;
		right = null;
	}

	public void insert(int v) 
	{
		if(v < value)
		{
			if(left == null)
			{
				left = new ProveNull(v);
			}
			else
			{
				left.insert(v);
			}					
		}
		else if(v > value)
		{
			if(right == null)
			{
				right = new ProveNull(v);
			}
			else
			{
				right.insert(v);
			}
		}
	}


/* 
 	findNullPointers() looks for dead ends or empty nodes,
	increments a count and returns that count
*/

   	int findNullPointers(int count)
	{     
		if(right != null){
			count = right.findNullPointers(count);
		}else{
			count++;
		}
		if(left != null){
			count = left.findNullPointers(count);	
		}else{
			count++;
		}
     	return count;
   	}

/*
	findNodes() traverses the tree looking for full nodes,
	incrementing a count and returing it for comparison to 
	the findNullPointers() count
*/

     public int findNodes(int count)
     {
	if(right != null){
		count = right.findNodes(count);
		count++;
	}
	if(left != null){
		count = left.findNodes(count);
		count++;
	}
	return count;
	}

	public static void main(String args[]){

		/*
			Create a three node tree to test
			the general case of N nodes for N+1 nulls
		*/

		ProveNull tree = new ProveNull(3);
		tree.insert(4);
		tree.insert(1);

		if((tree.findNullPointers(0)-tree.findNodes(1))!=1){
			System.out.println("There is not N+1 null pointers for N nodes");
			System.out.println("Null Pointers: "+tree.findNullPointers(0));
			System.out.println("Nodes: "+tree.findNodes(1));
		}else{
			System.out.println("There are N+1 null pointers for N nodes");
			System.out.print("Null Pointers: "+tree.findNullPointers(0));
			System.out.println(", Nodes: "+tree.findNodes(1));
		}

		/*
			Create a single node tree to prove
			the special case N =1
		*/
		
		ProveNull singleNode = new ProveNull(3);

		if((singleNode.findNullPointers(0)-singleNode.findNodes(1))!=1){
			System.out.println("There is not N+1 null pointers for N nodes");
			System.out.print("Null Pointers: "+singleNode.findNullPointers(0));
			System.out.println(", Nodes: "+singleNode.findNodes(1));
		}else{
			System.out.println("There are N+1 null pointers for N nodes");
			System.out.print("Null Pointers: "+singleNode.findNullPointers(0));
			System.out.println(", Nodes: "+singleNode.findNodes(1));
		}
	}


}