Tree Height After Deletions I
A rooted tree is given as [parent, child] edges plus its root. Some nodes are deleted: a deleted node's children are promoted to its nearest surviving ancestor, and its subtree is otherwise kept. The root is never deleted.
Return the height of the tree afterwards, counted in nodes — a lone root has height 1.
edges = [[1, 2], [1, 3], [3, 4], [3, 5], [5, 6]], root = 1 heightAfterDeletions(edges, 1, [3]) -> 3 // 1 -> 5 -> 6 heightAfterDeletions(edges, 1, []) -> 4 // 1 -> 3 -> 5 -> 6
Hints
Hint 1
Nothing needs rewiring. Walk the original tree carrying a depth, and have a deleted node pass its depth through unchanged while a surviving node adds one.
Hint 2
One traversal, iterative or recursive; the answer is the largest depth seen at a surviving node.