public static class BinaryTreeNodeCounter
{
    public static int CountNodes<T>(this IBinaryTree<T> tree)
    {
        if (tree == null)
        {
            return 0;
        }

        return 1 + CountNodes(tree.Left) + CountNodes(tree.Right);
    }
}

• how a tree (binary tree in particular) works
• the recursive definition of a binary tree
• recursive methods and how base cases stop recursion
• what counting a single node means
• (less important) knowledge of C# syntax
• interfaces as a contract
• generics
• extension methods

public static class BinaryTreeNodeCounter
{
    public static int CountNodes<T>(this IBinaryTree<T> tree)
    {
        return tree == null
            ? 0
            : 1 + tree.Left.CountNodes() + tree.Right.CountNodes();
    }
}

• how a tree (binary tree in particular) works
• the recursive definition of a binary tree
• recursive methods and how base cases stop recursion
• what counting a single node means
• interfaces as a contract
• (less important) knowledge of C# syntax:
• generics
• extension methods
• ternary operator

My favorite which encompasses a few disciplines is to count the number of nodes in a binary tree given the class (in C#):

public sealed class BinaryTree<T>
{
    private readonly BinaryTree<T> left;

    private readonly BinaryTree<T> right;

    private readonly T data;

    public BinaryTree(
        BinaryTree<T> left,
        BinaryTree<T> right,
        T data)
    {
        this.left = left;
        this.right = right;
        this.data = data;
    }

    public BinaryTree<T> Left
    {
        get
        {
            return this.left;
        }
    }
 

    public BinaryTree<T> Right
    {
        get
        {
            return this.right;
        }
    }
 

    public T Data
    {
        get
        {
            return this.data;
        }
    }

    // Other methods not germane to this problem.
}

public static class BinaryTreeNodeCounter
{
    public static int CountNodes(BinaryTree<T> tree)
    {
        // TODO: What goes here?
    }
}

public static class BinaryTreeNodeCounter
{
    public static int CountNodes(BinaryTree<T> tree)
    {
        if (tree == null)
        {
            return 0;
        }

        return 1 + CountNodes(tree.Left) + CountNodes(tree.Right);
    }
}

• how a tree (binary tree in particular) works
• the recursive definition of a binary tree
• recursive methods and how base cases stop recursion
• what counting a single node means
• (less important) knowledge of C# syntax

My favorite which encompasses a few disciplines is to count the number of nodes in a binary tree given the interface (in C#):

public interface IBinaryTree<T>
{
    IBinaryTree<T> Left
    {
        get;
    }

    IBinaryTree<T> Right
    {
        get;
    }

    T Data
    {
        get;
    }

    // Other properties and methods not germane to this problem.
}

and just for fun, here's the implementation, though the interviewee need not see this.

public sealed class BinaryTree<T> : IBinaryTree<T>
{
    private readonly IBinaryTree<T> left;

    private readonly IBinaryTree<T> right;

    private readonly T data;

    public BinaryTree(
        IBinaryTree<T> left,
        IBinaryTree<T> right,
        T data)
    {
        this.left = left;
        this.right = right;
        this.data = data;
    }

    public IBinaryTree<T> Left
    {
        get
        {
            return this.left;
        }
    }

    public IBinaryTree<T> Right
    {
        get
        {
            return this.right;
        }
    }

    public T Data
    {
        get
        {
            return this.data;
        }
    }

    // Other properties and methods not germane to this problem.
}

public static class BinaryTreeNodeCounter
{
    public static int CountNodes<T>(this IBinaryTree<T> tree)
    {
        // TODO: What goes here?
    }
}

public static class BinaryTreeNodeCounter
{
    public static int CountNodes<T>(this IBinaryTree<T> tree)
    {
        if (tree == null)
        {
            return 0;
        }

        return 1 + CountNodes(tree.Left) + CountNodes(tree.Right);
    }
}

• how a tree (binary tree in particular) works
• the recursive definition of a binary tree
• recursive methods and how base cases stop recursion
• what counting a single node means
• (less important) knowledge of C# syntax
• interfaces as a contract
• generics
• extension methods