Tree Levels After Node Deletions II

CodingPhone, OnsiteSoftware EngineerReported Oct, 2026High Frequency

Examples

Example 1:

Input: root = [1,2,3], targetHeight = 1

Output: 1

Explanation:

Example 2:

Input: root = [1,2,3,4,5], targetHeight = 2

Output: 1

Explanation:

Constraints

Discussion

You are given the root of a binary tree where each node value is a unique node ID, and an integer targetHeight.

Deletion rule:

When a node is deleted, it is removed and its existing children are promoted upward to the deleted node's parent level.
If multiple deleted nodes appear on a path, keep promoting descendants upward until they connect to the nearest non-deleted ancestor (or become a root if none exists).

After deletions, the result may be a forest. Define final height as the maximum number of levels among all remaining trees (0 if all nodes are deleted).

Return the minimum number of nodes you must delete so that final height is less than or equal to targetHeight.

Delete node 1, then nodes 2 and 3 become roots and final height is 1.

Deleting node 2 (or 1) is enough to make final height at most 2.

1 <= Number of nodes <= 15

-10^4 <= Node.val <= 10^4

Node.val values are unique.

0 <= targetHeight <= Number of nodes