Height of Binary Tree After Subtree Removal Queries

Height of Binary Tree After Subtree Removal Queries - Problem

You are given the root of a binary tree with n nodes. Each node is assigned a unique value from 1 to n. You are also given an array queries of size m.

You have to perform m independent queries on the tree where in the i^th query you do the following:

Remove the subtree rooted at the node with the value queries[i] from the tree. It is guaranteed that queries[i] will not be equal to the value of the root.

Return an array answer of size m where answer[i] is the height of the tree after performing the i^th query.

Note:

The queries are independent, so the tree returns to its initial state after each query.
The height of a tree is the number of edges in the longest simple path from the root to some node in the tree.

Input & Output

Example 1 — Basic Tree

$ Input: root = [1,3,4,2,null,6,5,null,null,null,null,null,7], queries = [3,6,4,5]

› Output: [3,3,2,2]

💡 Note: After removing node 3: height becomes 3 (path 1→4→5→7). After removing node 6: height becomes 3 (path 1→4→5→7). After removing node 4: height becomes 2 (path 1→3→2). After removing node 5: height becomes 2 (path 1→3→2).

Example 2 — Smaller Tree

$ Input: root = [5,8,9,2,1,3,7,4,6], queries = [3,2,4,8]

› Output: [3,2,3,2]

💡 Note: After removing different subtrees, the remaining tree has various maximum heights depending on which nodes remain and their depths.

Constraints

The number of nodes in the tree is n.
2 ≤ n ≤ 10⁵
1 ≤ Node.val ≤ n
All the values in the tree are unique.
m == queries.length
1 ≤ m ≤ min(n, 10⁴)
1 ≤ queries[i] ≤ n
queries[i] ≠ root.val

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with unique node values 1 to n

Remove Subtree

Remove the subtree rooted at the queried node

Calculate Height

Find the height of the remaining tree structure

Key Takeaway

🎯 Key Insight: Precompute alternative heights using DFS to answer queries in O(1) time instead of recalculating each time

Asked in

G Google 15 a Amazon 12 f Meta 8 M Microsoft 6

The key insight is to precompute alternative heights using DFS traversal instead of recalculating for each query. We perform two DFS passes: first to calculate subtree heights, then to compute what the tree height would be if each node's subtree is removed. Best approach is DFS Precomputation with Time: O(n + m), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Remove and Recalculate	O(m × n)	O(h)	For each query, remove the subtree and calculate height of remaining tree
DFS Precomputation with Alternative Heights	O(n + m)	O(n)	Pre-calculate heights and alternative paths using DFS traversal

Brute Force - Remove and Recalculate — Algorithm Steps

Step 1: For each query, mark the subtree to be removed
Step 2: Traverse the tree skipping the marked subtree
Step 3: Calculate the maximum depth of remaining nodes

Visualization

Tap to expand

Step-by-Step Walkthrough

Original Tree

Tree with all nodes present

Remove Subtree

Skip the queried subtree during traversal

Calculate Height

Find maximum depth of remaining nodes

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int calculateHeight(struct TreeNode* root, int skipVal) {
    if (!root || root->val == skipVal) return -1;
    int leftHeight = calculateHeight(root->left, skipVal);
    int rightHeight = calculateHeight(root->right, skipVal);
    return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}

int* solution(struct TreeNode* root, int* queries, int queriesSize, int* returnSize) {
    *returnSize = queriesSize;
    int* result = (int*)malloc(queriesSize * sizeof(int));
    for (int i = 0; i < queriesSize; i++) {
        result[i] = calculateHeight(root, queries[i]);
    }
    return result;
}

int main() {
    // Simplified tree building for demo - create a sample tree
    struct TreeNode* root = createNode(1);
    root->left = createNode(3);
    root->right = createNode(4);
    root->left->left = createNode(2);
    root->right->left = createNode(6);
    root->right->right = createNode(5);
    root->right->right->right = createNode(7);
    
    int queries[] = {3, 6, 4, 5};
    int queriesSize = 4;
    int returnSize;
    
    int* result = solution(root, queries, queriesSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m × n)

For each of m queries, we traverse up to n nodes to calculate height

✓ Linear Growth

Space Complexity

O(h)

Recursion stack depth is at most the tree height h

✓ Linear Space

15.0K Views

Medium Frequency

~35 min Avg. Time

340 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Remove and Recalculate — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler