Binary Tree Multithreaded Time Complexity
[..], then wouldn't the big $\mathcal{O}$ time complexity be $\mathcal{O}(\log n)$


People often forget that big-$\mathcal{O}$ notation only is meaningful in a certain context, here this becomes obvious:

You are probably used to count some set of instructions (like comparing, adding etc.) as one unit - called unit cost model - each instruction happening sequentially. In that model you're right, traversal and outputting every vertex of a binary tree is $\Omega(n)$ (ie. you cannot do better than linear).

However when talking about parallel algorithms and their complexity things change, first of all you will need to specify $p$ how many processors you use1. You will also need to specify  whether multiple processors have exclusive or concurrent access for reading/writing.

You were probably talking about the CREW (concurrent read, exclusive write) PRAM and assumed $p = n$ in your question:


  you could never traverse an entire tree in less than $\mathcal{O}(n)$


In total all the processors will have looked at $\mathcal{O}(n)$ vertices in the binary tree, this does not change and is called the work.

You were right that the time complexity (refered to as depth) is $\mathcal{O}(\log n)$ for that algorithm.



To illustrate my point even more, assume that the binary tree is given as an array with a certain order and still using $n$ processors with a CREW machine. Now, every (numbered) machine can simply lookup the value at its position in that array.

This algorithm has still $\mathcal{O}(n)$ work, but $\mathcal{O}(1)$ depth.

Conclusion

Always be aware of the context (eg. what model, what input format) since this has a great influence on the complexity. Once you introduce parallelism things become different and it's important to be precise about what assumption you make and how many processors an algorithm uses.



1: From now on I will assume a parallel random-access machine since it's very simple but still useful.