# Dynamic Programming Problem on Tree

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)$$?

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.