2
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – JhonRayo99 Feb 1 at 11:18
  • $\begingroup$ Ahh yes I only explain the complexity of that one case. I have updated the post to contain a worst-case complexity. $\endgroup$ – Throckmorton Feb 1 at 16:48
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.