Given a tree $T$ rooted at $1$. Each node might have more than 2 children. You want to create a tree $S$ where each node have $2$ or less children or a binary tree. For each node $u$ in $T$ which had more than $2$ children. Let $D$ be the number of $u$'s children. You can add $D-2$ node to replace the edge connecting $u$ and its children to form a new tree where $u$ is the root and the leaf nodes are its children. There are many possible ways to create $S$. Find the minimum depth of $S$ where depth is the maximum distance from root to some leaves.

My idea is to use Dynamic Programming approach. Let $dp[u]$ be the minimum depth we can make for subtree which $u$ is the root. Let $v$ be the child node of $u$. My approach is to sort $dp[v]$ in descending order and then use Dynamic Programming on the sorted list in $O(n^3)$. Similar to the solution of Matrix Chain Multiplication. But this approach is too slow. Is there any greedy solution so that I can calculate $dp[u]$ in $O(n)$ or $O(n log n)$?


1 Answer 1


So the difficulty is to determine $dp[u]$, depth of $u$, starting from the list of its sons depths $L[dp[v]]$.

Once $L[dp[v]]$ is sorted in a heap, you can recursively and greedily pop the 2 minimum values $i$, $j$ and push $1+max(i, j)$.

For instance, $L[dp[v]] = [7,5,5,4,3,2,2]$:

=> [7,5,5,4,3,3]
=> [7,5,5,4,4]
=> [7,5,5,5]
=> [7,6,5]
=> [7,7]

$dp[u] = 8$

This is actually $O(nlog(n))$ due to the heap sort.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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