The time complexities for BFS and DFS are just O(|E|), or in your case, O(m).
In a binary tree, m is equal to n-1 so the time complexity is equivalent to O(|V|). m refers to the total number of edges, not the average number of adjacent edges per vertex.