Snowflake·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

Snowflake SWE interview with a tree manipulation problem that looked manageable on the surface but had some tricky edge cases once you got into the deletion logic.

Questions Asked (1)

Given the root of an N-ary tree and a set of node values to delete, implement the deletions such that each deleted node's children are promoted to take its place under its parent. The root is guaranteed not to be in the delete set. Return the maximum height of the resulting tree, where height is measured in edges.

Algorithms & Data Structures

Author's notes

The promotion logic is where I got tangled.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a post-order DFS to process the tree bottom-up, deleting nodes and promoting their children to the parent. At each node, compute the height of the resulting subtree after deletions, and return the maximum height of the root's subtree.

Pro tip: Clarify with the interviewer whether the height should be computed after all deletions or if deletions can be done in any order; also discuss edge cases like deleting a leaf or a node with multiple children.

1. Understand the problem and constraints

Confirm that the root is never deleted, and that height is measured in edges. Clarify that deletions are simultaneous and children are promoted to the deleted node's parent.

2. Choose a traversal strategy

Use post-order DFS because deletions affect the subtree structure, and we need to compute heights bottom-up after modifications.

3. Process each node recursively

For each node, recursively process its children. If the node is to be deleted, return its children's processed results to be attached to its parent; otherwise, compute its height as 1 + max(children heights).

4. Handle deletions and promotions

When a node is deleted, its children (after their own deletions) are promoted to the parent. Ensure the parent's children list is updated accordingly.

5. Compute and return the final height

After processing the root, return the maximum height of the resulting tree. If the root has no children, height is 0.

Key Points to Mention

Post-order DFS ensures children are processed before their parent, which is necessary for correct promotion.
When a node is deleted, its children must be promoted to its parent, so the parent's children list needs to be updated.
Height of a node is 1 + maximum height among its children (after deletions), with leaf nodes having height 0.
The root is never deleted, so the final height is computed from the root's subtree.
Time complexity is O(N) where N is the number of nodes, as each node is visited once.
Space complexity is O(H) for recursion stack, where H is the height of the original tree, or O(N) in the worst case.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.