What you need is the following observation/result:
Proposition: A graph is bipartite if and only if the set of vertices/nodes can be partitioned into two subsets in such a way that in a given subset, no two vertices are connected.
Think about it a little while, and it should become clear. But then, you see that a graph without cycles is clearly bipartite. For if you have a tree, choose a root. Then you put this root in one set; you put its neighbours in the second set; you put the neighbours' neighbours in your first set, etc. Since there is no cycle, for any choice of two vertices in a given subset, they won't be adjacent.
Now, if you have a forest, partition each tree separately.
This is the way I would prove that a forest is bipartite, but this is only because I am more familiar with the definition involving a partition of the vertex set. On the other hand, for vacuous reasons, a forest is bipartite, exactly because it does not have any odd cycle (since it does not have any cycle). However, sometimes it happens that we are reluctant to believe something is true for vacuous reasons. This is why I wrote the above solution.
The comment was too short.
Your correctness proof is hardly there. I also don't know what do you mean by 'comparisons' and where from you got $2|E|$. On the other hand, this is a correct algorithm given you have a connected graph. Your comment explains what to do in disconnected case, but then you could just apply it, after all, one searches for the connected components with DFS (and those two DFSes could be just one). Moreover, one can do initialization faster, the $|V|$ part of complexity should come from the fact that in the worst case you will have to visit (or at least take care in some way) all the vertices. Of course, if you have initialization done this way, you ought to mention it (as you did; besides this is not a big fault, usually you need to read the graph from some kind of input and this is where you can initialize your arrays/maps).
Finally, this is a fine attempt, you shouldn't be discouraged. There are some issues, but I would be glad if my students had enough patience and precision to work it out as you did.
As for suggestions for complexity, the best way is to express the number of operations in your algorithm depending on some global properties, like "my algorithm visits every vertex at most 42 times and every edge at most 78" or "for every edge it does at most $|V|^{567}$ operations" and so on.
As for suggestions for correctness, one usually splits the proof into two parts: "if cycle exists, then my algorithm will return true" (or "if my algorithm returns false then graph is a forest"), and "if my algorithm returns true, then cycle exists" (or "if cycle doesn't exists, my algorithm will return false"). This is not the fastest way, but it is very easy to do serious mistakes if you prove both implications at the same time.
I hope you will find my advice usefull.
Best Answer
Can we consider the following example:
$G=(V,E)$ with $V=\{1,2,3\}$, $E=\{(1,2),(2,3),(1,3)\}$ and root designated to $1$, in which there is no cycle but $3$ is visited more than twice.