How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Snowflake.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Snowflake during technical interviews.

Compute height of tree with deleted nodes; minimize deletions

Quick Overview

This question evaluates understanding of tree data structures, connectivity after node deletions, and optimization for minimizing additional removals, and is categorized under Coding & Algorithms. It is commonly asked to assess reasoning about tree pruning and height computation under constraints, testing both conceptual understanding of tree properties and practical algorithmic implementation.

Compute height of tree with deleted nodes; minimize deletions

Company: Snowflake

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given a rooted tree (not necessarily binary). Each node has a list of children. Some nodes are marked as `deleted = true`. Define the **effective tree** as the tree after removing every deleted node and all edges incident to it; nodes that become disconnected from the root are not counted. 1) Compute the **height** of the effective tree (maximum number of nodes on any root-to-leaf path in the effective tree; if the root is deleted, the height is 0). 2) Follow-up: Given an integer `K`, delete the **minimum number of additional nodes** (you may choose any nodes to delete) so that the height of the effective tree is **at most `K`**. Return that minimum number of additional deletions. Clarify in your solution what “deleting a node” means (assume a deleted node is removed and you cannot traverse through it from the root).

Quick Answer: This question evaluates understanding of tree data structures, connectivity after node deletions, and optimization for minimizing additional removals, and is categorized under Coding & Algorithms. It is commonly asked to assess reasoning about tree pruning and height computation under constraints, testing both conceptual understanding of tree properties and practical algorithmic implementation.

Part 1: Height of the Effective Tree

You are given a rooted tree with nodes labeled 0 to n - 1, where node 0 is the root when n > 0. Each node has a list of children, and some nodes are already marked as deleted. A deleted node is removed from the tree, you cannot traverse through it from the root, and any descendants that become disconnected from the root are ignored. Compute the height of the effective tree after these deletions. The height is the maximum number of nodes on any root-to-leaf path in the effective tree. If the root is deleted, or the tree is empty, the height is 0.

Constraints

0 <= n <= 200000
If n > 0, node 0 is the root
children describes a valid rooted tree with no cycles
When n > 0, the total number of child references is n - 1
deleted has length n

Examples

Input: (5, [[1, 2], [3, 4], [], [], []], [False, False, False, False, False])

Expected Output:

Explanation: All nodes are present. The longest root-to-leaf path is 0 -> 1 -> 3 or 0 -> 1 -> 4, so the height is 3.

Input: (6, [[1, 2], [3], [4, 5], [], [], []], [False, True, False, False, False, False])

Expected Output:

Explanation: Node 1 is deleted, so node 3 becomes disconnected and is ignored. The longest remaining path is 0 -> 2 -> 4 or 0 -> 2 -> 5.

Input: (3, [[1, 2], [], []], [True, False, False])

Expected Output:

Explanation: The root is deleted, so the effective tree is empty.

Input: (0, [], [])

Expected Output:

Explanation: An empty tree has height 0.

Hints

Start a DFS or BFS from the root. Never move into a deleted node.
Track depth as the number of nodes on the current path, not the number of edges.

Part 2: Minimum Additional Deletions to Limit Height

You are given a rooted tree with nodes labeled 0 to n - 1, where node 0 is the root when n > 0. Some nodes are already marked as deleted. A deleted node is removed, you cannot traverse through it from the root, and any descendants that become disconnected from the root are ignored. In addition to the existing deleted nodes, you may delete any non-root node. Your goal is to make the height of the effective tree at most K while deleting as few additional nodes as possible. Height is measured as the number of nodes on a root-to-leaf path. If the tree is empty or the root is already deleted, the answer is 0.

Constraints

0 <= n <= 2000
If n > 0, node 0 is the root
children describes a valid rooted tree with no cycles
When n > 0, the total number of child references is n - 1
deleted has length n
1 <= K <= 2000
n * K <= 2000000
Only non-root nodes may be additionally deleted

Examples

Input: (6, [[1, 2], [3, 4], [5], [], [], []], [False, False, False, False, False, False], 2)

Expected Output:

Explanation: To keep height at most 2, the subtree under node 1 must be cut and the subtree under node 2 must also be cut. Deleting nodes 1 and 2 is optimal.

Input: (4, [[1], [2], [3], []], [False, False, False, False], 2)

Expected Output:

Explanation: Deleting node 2 makes the remaining effective tree 0 -> 1, whose height is 2.

Input: (5, [[1], [2], [3], [4], []], [False, False, True, False, False], 2)

Expected Output:

Explanation: Node 2 is already deleted, so nodes 3 and 4 are disconnected. The effective tree is just 0 -> 1 and already has height 2.

Input: (3, [[1, 2], [], []], [True, False, False], 1)

Expected Output:

Explanation: The root is already deleted, so the effective tree is empty.

Input: (1, [[]], [False], 1)

Expected Output:

Explanation: A single-node tree already has height 1, so no additional deletions are needed.

Hints

Think bottom-up. If you keep a node and allow height h from that node downward, each child must either be deleted or be reduced to height h - 1.
Define a DP state for keeping node u with remaining allowed height h.

Last updated: Jun 8, 2026

Loading coding console...

Quick Overview

Compute height of tree with deleted nodes; minimize deletions

Company: Snowflake

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

Part 1: Height of the Effective Tree

Constraints

0 <= n <= 200000
If n > 0, node 0 is the root
children describes a valid rooted tree with no cycles
When n > 0, the total number of child references is n - 1
deleted has length n

Examples

Input: (5, [[1, 2], [3, 4], [], [], []], [False, False, False, False, False])

Expected Output:

Explanation: All nodes are present. The longest root-to-leaf path is 0 -> 1 -> 3 or 0 -> 1 -> 4, so the height is 3.

Input: (6, [[1, 2], [3], [4, 5], [], [], []], [False, True, False, False, False, False])

Expected Output:

Explanation: Node 1 is deleted, so node 3 becomes disconnected and is ignored. The longest remaining path is 0 -> 2 -> 4 or 0 -> 2 -> 5.

Input: (3, [[1, 2], [], []], [True, False, False])

Expected Output:

Explanation: The root is deleted, so the effective tree is empty.

Input: (0, [], [])

Expected Output:

Explanation: An empty tree has height 0.

Hints

Start a DFS or BFS from the root. Never move into a deleted node.
Track depth as the number of nodes on the current path, not the number of edges.

Part 2: Minimum Additional Deletions to Limit Height

Constraints

0 <= n <= 2000
If n > 0, node 0 is the root
children describes a valid rooted tree with no cycles
When n > 0, the total number of child references is n - 1
deleted has length n
1 <= K <= 2000
n * K <= 2000000
Only non-root nodes may be additionally deleted

Examples

Input: (6, [[1, 2], [3, 4], [5], [], [], []], [False, False, False, False, False, False], 2)

Expected Output:

Explanation: To keep height at most 2, the subtree under node 1 must be cut and the subtree under node 2 must also be cut. Deleting nodes 1 and 2 is optimal.

Input: (4, [[1], [2], [3], []], [False, False, False, False], 2)

Expected Output:

Explanation: Deleting node 2 makes the remaining effective tree 0 -> 1, whose height is 2.

Input: (5, [[1], [2], [3], [4], []], [False, False, True, False, False], 2)

Expected Output:

Explanation: Node 2 is already deleted, so nodes 3 and 4 are disconnected. The effective tree is just 0 -> 1 and already has height 2.

Input: (3, [[1, 2], [], []], [True, False, False], 1)

Expected Output:

Explanation: The root is already deleted, so the effective tree is empty.

Input: (1, [[]], [False], 1)

Expected Output:

Explanation: A single-node tree already has height 1, so no additional deletions are needed.

Hints

Think bottom-up. If you keep a node and allow height h from that node downward, each child must either be deleted or be reduced to height h - 1.
Define a DP state for keeping node u with remaining allowed height h.

Last updated: Jun 8, 2026

Loading coding console...