Medium Problems

Trees

Minimum height of a tree

Q: Given a tree , find all the roots that make the minimum height.

Solution 1: time

• Find any longest path in the tree, the answer is its middle points.
• Finding a longest path can be soved in linear time by a tree dp, or by two BFS.

Solution 2: time

• Use direct dp, let dp[i] be the height of tree when the root is i , compute dp[0] ,…, dp[n-1] by tree dp in DFS manner.
• In DFS, when we reach a node u , let T be the subtree by removing all decendants of u . We also matain a variable acc that keeps track of the length of the longest path in T with u being one end. Then we have dp[u] = max(height[u], acc)
• In DFS, when we move from u to its child v , then newAcc = max(acc+1, height[v']+2) for all other children of u . We can compute it in constant time by maintaining two heights of each node u , one is the conventional height, the other is the height by removing the branch w.r.t. to the conventional height. In other words, we maintain the largest two heights of u’s children.

Solution 3: time

• Iterately prune leaves. Use set to denote adjancency.

Leetcode for solution 1 and 2
Leetcode for solution 3

Verify a shortest path tree

Q: Professor Gaedel has written a program that he claims implements Dijkstra’s algorithm. The program produces and for each vertex . Give an -time algorithm to check the output of the professor’s program. It should determine whether the and attributes match those of some shortest-paths tree. You may assume that all edge weights are nonnegative.
(The problem is from CLRS 24.3-4)

Solution:

• First check whether compose a -rooted tree.
• Then check that and and is the minimizer.
• If all are true, return true. Otherwise, return false.

  It seems that this algorithm works for negative edges, doesn’t it?