Time complexity - Algorithm to find the lowest common ancestor of all deepest leaves
As @Rick Decker explained, you could have $n/2$ leaves at the max depth in the one case. In this case, step 3 is $O(n\log n)$. This post shows the worst case. Consider a tree $T$ consists of a chain of $n/2$ nodes where the remaining $n/2$ nodes are attached as a balanced tree at the bottom of the chain. This gives every leaf depth $n/2+\log_2(n)=\Theta(n)$ With $n/4$ leaves at depth $\Theta(n)$ we have $\Theta(n^2)$ runtime for step 3 in this case. This is asymptotically the worst case since we have $n$ nodes at max depth $n$. 

There's a better way to do this. Lets define a function $f$

$
f(v) =  \begin{cases}
v &amp; \text{if}\quad \texttt{height}(v.left) = \texttt{height}(v.right) \\
f(v.left) &amp; \text{if}\quad \texttt{height}(v.left) &gt; \texttt{height}(v.right) \\
f(v.right) &amp; \text{if}\quad \texttt{height}(v.left) &lt; \texttt{height}(v.right) 
\end{cases}
$

If the heights of the children of a node $v$ are the same, then clearly $v$ is the LCA of the deepest nodes of the subtree rooted at $v$. If the left subtree is taller, then we want the LCA of the deepest nodes of the subtree rooted at $v.left$, since they are deeper than the deepest nodes in the subtree rooted at $v.right$. The same logic follows for $v.right$ when it is taller. 

The values for $\texttt{height}$ and $f(v)$ can be computed in a post-order traversal of $T$ in linear time.

Calling $f(root)$ should return the LCA of the deepest nodes in the tree.