Logical error BST ... wrong results

Answer 1

If what you mean in CountNodes is to count all non-leaf nodes you must change this line:

int count=1;

to read this:

int count = (root._left == null && root._right == null) ? 0 : 1;

(the opposite of what is in CountLeaves).

And this will get you the height of the tree:

public int Height(TreeNode root)
{
    int height = 1;
    if (root._left != null)
        height = Math.Max(height, Height(root._left));
    if (root._right != null)
        height = Math.Max(height, Height(root._right));
    return height;   
}

Answer 2

Regarding getting the tree height, use the following recursive pseudo-code, calling nodeHeight(root):

nodeHeight(node)
    left=0
    right=0

    if (node == null) return 0

    left = 1 + nodeHeight(getLeft(node))
    right = 1 + nodeHeight(getRight(node))

    return max(left,right)

Answer 3

It doesn't appear that you balance your tree, so you just get a simple linked list, that may account for your incorrect values. A properly balanced tree will have a maximum height of log2(n).