title: Is the runtime of BFS and DFS on a binary tree O(N)?
body: <p>I realize that runtime of BFS and DFS on a generic graph is O(n+m), where n is number of nodes and m is number of edges, and this is because for each node its adjacency list must be considered. However, what is the runtime of BFS and DFS when it is executed on a binary tree? I believe it should be O(n) because the possible number of edges that can go out of a node is constant (i.e., 2). Please confirm if this is the correct understanding. If not, then please explain what is the correct time complexity of BFS and DFS on a binary tree?</p>