Time complexity - Algorithm to find the lowest common ancestor of all deepest leaves

This is the problem statement I came across today.

Given a binary tree, find the lowest common ancestor of all deepest leaves.

I came up with a correct algorithm, but I would like to confirm the running time of this approach.

The algorithm is as follows:

1. Traverse the tree and find the deepest level of the tree, dmax.
2. Traverse the tree and find all leaves at depth dmax.
3. Given that LCA(A,B,C) = LCA(LCA(A,B),C), traverse all nodes found at step 2 and calculate LCA.

The subroutine for LCA(A,B) is simple. Starting at A, go all the way up to the root and store each visited node in a hashset. Then, starting at B, go up until you find a node which is contained in the hashset.

I know the first two steps of the algorithm are both O(n), where n corresponds to the number of nodes in the tree. However, I am uncertain about the last step.

LCA(A,B) subroutine has a linear complexity. But how many nodes, in the worst scenario, can be found at step 2?.

Intuitively, I would argue that it has to be far less than n nodes.

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 & \text{if}\quad \texttt{height}(v.left) = \texttt{height}(v.right) \\ f(v.left) & \text{if}\quad \texttt{height}(v.left) > \texttt{height}(v.right) \\ f(v.right) & \text{if}\quad \texttt{height}(v.left) < \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.

• is step 3 O(nlgn)? I guess in the case mentioned by @Rick Decker the height of the tree would be lgn, meaning the LCA subroutine would be O(lgn). However, wouldn't in general be O(n^2)? Because the height could potentially be upper bounded by n. Just wanted to get some clarification here Commented Feb 1, 2020 at 11:18
• Ahh yes I only explain the complexity of that one case. I have updated the post to contain a worst-case complexity. Commented Feb 1, 2020 at 16:48

Well, I don't know what you intend by "far less than" but it's clear that you could have about $$n/2$$ leaves at maximum depth: take a complete binary tree, for example, with the lowest level full.

I'd write a function which for each tree calculates the lowest common ancestor of all deepest nodes, and the height of the tree. This is quite simple:

If the root R has no left or right branch, then the height is 1 and the common ancestor is R. If the root R has either a left or right branch, then calculate height and lowest common ancestor of that branch, and the height with root R is one higher, but the lowest common ancestor is the same.

If there is a left and a right branch, then calculate height and lowest common ancestor of both branches. If the heights are different, then we return (height + 1) plus the lowest ancestor of that branch. If the heights are the same, then we return (height + 1), and R as the lowest common ancestor.

That should take cN steps with a small constant c if the number of nodes is N. And since we must visit every node N (at least to know that it has no branches), this cannot be improved upon.