In a breadth-first search (BFS) algorithm on a tree, each node is visited exactly once, and each edge is traversed once. As a tree has N-1 edges for N nodes, the time complexity of BFS on a tree is proportional to the number of nodes, denoted as O(N).