Minimum Height
Snowflake● MediumINTERNOAProblem statement
A database is represented as a rooted tree with tree_nodes tables, where Table 1 is the root.
Up to max_operations operations are allowed. In one operation:
- Select a child table
uof a parent tablevand remove the edge betweenuandv. - Move
uand its subtree to become a direct child of the root, reducing its depth.
Determine the minimum possible height of the tree.
Note:
- The height of the tree is defined as the maximum depth of any table.
- The depth of a table is the number of edges from the root to that table.
- A subtree in a rooted tree is a subgraph of the tree consisting of a vertex, the root of that subtree, and its descendants, along with all edges incident to these descendants.
Function
getMinimumHeight(tree_nodes: int, tree_from: int[], tree_to: int[], max_operations: int) → int Complete the function getMinimumHeight in the editor with the following parameters:
int tree_nodes: the number of nodes in the treeint tree_from[tree_nodes - 1]: the starting node of the edgeint tree_to[tree_nodes - 1]: the ending node of the edgeint max_operations: the maximum number of operations
Returns int: the minimum possible height of the tree after as many as max_operations operations
Examples
Example 1
tree_nodes = 4tree_from = [3, 1, 2]tree_to = [2, 3, 4]max_operations = 1return = 21324
One possible operation can be:
- Remove the edge
(2, 4)and add an edge(1, 4).
4132
So, the height of the tree is 2.