Is BFS and DFS runtime in binary tree O (N)?

Question

I understand that the runtime of BFS and DFS on the general graph is O (n + m), where n is the number of nodes and m is the number of edges, and this is because for each node its adjacency list should be considered. However, what is the BFS and DFS runtime environment when it runs on a binary tree? I believe this should be O (n), because the possible number of edges that can exit the node is constant (i.e. 2). Please confirm if this is correct. If not, then please explain what is the correct time complexity of BFS and DFS on a binary tree?

Answer 1

The temporary difficulties for BFS and DFS are simply O(|E|) , or in your case O(m) .

In a binary tree, m is 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 at the vertex.

Answer 2

Yes, O (n) is correct.

Also note that the number of edges is more accurately expressed by the number of nodes - 1. This can be easily seen, considering that each node, with the exception of the root, has an edge from its parent to itself, and these edges cover all the edges that exist in the tree.