Tree Question Snowflake
Gavin Ebenezer
1090
TreeSnowflakeBinary TreeInterview

Looking for some help on optimizing solution to this problem

Minimize Deletions to Target Tree Height

You are given the root of a binary tree and a target integer k.

The height of a tree is defined as the number of nodes on the longest path from the root to any leaf.

You can perform an operation on any node: "delete" it. A "deleted" node is not removed from the tree structure. Instead, it is bypassed when calculating the height. For any given root-to-leaf path, the number of deleted nodes on that path is not counted towards its length.

For example, on a path A -> B -> C, the height is 3. If node B is "deleted", the path for height calculation becomes A -> C, and its new length is 2.

Your Goal:
Find a set of nodes to delete such that the new height of the tree is at most .

Optimization:
You must find a solution that uses the minimum possible number of deletions.

Tie-Breaker:
If there are multiple sets of nodes that all achieve this minimum count, you must return the set that prioritizes deleting nodes at a greater depth (farther from the root). Formally, you must return the set that maximizes the sum of the depths of the deleted nodes, where depth(root) = 1.

Return a set containing the TreeNode objects that should be deleted.

Example 1:

Input:

    A (1)
   /
  B (2)
 /
C (3)

k = 2

Original Height: 3 (path A->B->C)

Possible Solutions (min count = 1):

  1. Delete {A}: New path B->C. Height = 2. Sum of depths = 1.
  2. Delete {B}: New path A->C. Height = 2. Sum of depths = 2.
  3. Delete {C}: New path A->B. Height = 2. Sum of depths = 3.

Output: {C}
Explanation: All three options achieve the minimum deletion count of 1. We apply the tie-breaker and choose the set with the maximum sum of depths. {C} has a sum of 3, which is the highest.

Example 2:

Input:

      A (1)
     / \
  B (2)   C (2)
  /       \
D (3)     E (3)

k = 2

Original Height: 3 (paths A->B->D and A->C->E)

Possible Solutions:

  1. Delete {A}: Min count = 1.
    • New paths: B->D (height 2) and C->E (height 2).
    • New tree height = 2.
    • Sum of depths = 1.
  2. Delete {D, E}: Min count = 2.
    • New paths: A->B (height 2) and A->C (height 2).
    • New tree height = 2.
    • Sum of depths = 3 + 3 = 6.
  3. Delete {B, C}: Min count = 2.
    • New paths: A->D (height 2) and A->E (height 2).
    • New tree height = 2.
    • Sum of depths = 2 + 2 = 4.

Output: {A}
Explanation: The primary goal is to find the minimum number of deletions. Option 1 achieves the goal with 1 deletion, while the others require 2. The tie-breaker rule is not applied because the minimum counts are not equal.

Example 3:

Input:

    A (1)
   /
  B (2)
 / \
C   D
(3) (3)

k = 2

Original Height: 3 (paths A->B->C and A->B->D)

Possible Solutions:

  1. Delete {B}: Min count = 1. New paths A->C, A->D. Height = 2. Sum of depths = 2.
  2. Delete {A}: Min count = 1. New paths B->C, B->D. Height = 2. Sum of depths = 1.
  3. Delete {C, D}: Min count = 2.

Output: {B}
Explanation: Both {A} and {B} achieve the minimum deletion count of 1. We apply the tie-breaker: sum_depths({B}) = 2 is greater than sum_depths({A}) = 1.

Comments (5)