Tail Recursion (Binary Search Tree height() implementation)

Ok, so I am in a Data Structures class that uses Java for language. We are currently studying different types of Binary Search Trees. But before our last test we went into detail about recursion and tail recursion. I missed the lecture that went into tail recursion and am trying to build an understanding of it on my own. I need to know two things essentially:

1. What is the difference between a recursive (non tail-recursive form) and tail recursive implementation (example if possible)?

2. When is it beneficial to use either a non-tail recursive implementation or a tail recursive implementation. Or is one always or efficient than the other?

Currently I am building up a BinarySearchTree class and I am currently implementing a height() function which uses recursion. I was wondering if either of these implementations use tail recursion. And either way would one of these implementations have better performance than the other?

First implementation:


	/**

	 * Recursively returns the height of a particular

	 * subtree.

	 *

	 * @param The subtree to calculate height of

	 * @return The height of the subtree

	 */

	public int height(BSTNode tree)

	{

		if (tree == null)

		{

			return 0;

		}

	

		int left = height(tree.getLeft());

		int right = height(tree.getRight());

	

		return 1 + Math.max(left, right);

	}

	

	/**

	 * @return The height of the entire tree

	 */

	public int height()

	{

		return height(root);

	}

Second implementation:


	/**

	 * Recursively returns the height of a particular

	 * subtree.

	 *

	 * @param The subtree to calculate height of

	 * @return The height of the subtree

	 */

	public int height(BSTNode tree)

	{

		if (tree == null)

		{

			return 0;

		}

	

		return 1 + Math.max(height(tree.getLeft(), tree.getRight());

	}

	

	/**

	 * @return The height of the entire tree

	 */

	public int height()

	{

		return height(root);

	}