Is the runtime of BFS and DFS on a binary tree O(N)?

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.