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:
- Traverse the tree and find the deepest level of the tree, dmax.
- Traverse the tree and find all leaves at depth dmax.
- 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.