Height of Binary Tree After Subtree Removal Queries

#1066 Most AskedHard

Height of Binary Tree After Subtree Removal Queries #1066 Most Asked

Hard

9 views

Topics:

TreesRecursion

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.

Example 1:

Input: root = [1,3,4,2,null,6,5,null,null,null,null,null,7], queries = [4]
Output: [2]
Explanation: The diagram above shows the tree after removing the subtree rooted at node with value 4.
The height of the tree is 2 (The path 1 -> 3 -> 2).

Example 2:

Input: root = [5,8,9,2,1,3,7,4,6], queries = [3,2,4,8]
Output: [3,2,3,2]
Explanation: We have the following queries:
- Removing the subtree rooted at node with value 3. The height of the tree becomes 3 (The path 5 -> 8 -> 2 -> 4).
- Removing the subtree rooted at node with value 2. The height of the tree becomes 2 (The path 5 -> 8 -> 1).
- Removing the subtree rooted at node with value 4. The height of the tree becomes 3 (The path 5 -> 8 -> 2 -> 6).
- Removing the subtree rooted at node with value 8. The height of the tree becomes 2 (The path 5 -> 9 -> 3).

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the tree and the number of queries? Specifically, what are the maximum values for the number of nodes in the tree and the length of the queries array?
Can the values of the nodes in the tree be negative, zero, or non-unique?
How is the tree represented? Is it passed as a `TreeNode` object, or some other format like an array or list of nodes and parent pointers?
If removing a subtree results in a disconnected forest, how do we define the 'height of the binary tree'? Is it the maximum height of any tree in the forest, or is it zero?
If a query asks to remove a node that doesn't exist in the tree, should I ignore the query, throw an error, or return a specific value?

Brute Force Solution

Approach

We want to find the height of a tree after removing subtrees. A brute force method would involve directly simulating the removal of each subtree and then recalculating the tree's height from scratch for each removal.

Here's how the algorithm would work step-by-step:

For each subtree we need to remove, imagine physically cutting it away from the main tree.
After cutting away a subtree, rebuild the entire tree structure that remains.
Once the tree is rebuilt without the cut subtree, figure out the height of the new tree by traversing all of its branches.
Record the height we calculated.
Do this for every subtree removal we are asked about.
In the end, we will have a list of tree heights, each corresponding to a specific subtree removal. These are our answers.

Code Implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def height_after_subtree_removal_brute_force(root, queries):
    results = []

    for node_to_remove_value in queries:
        # Simulate removing the subtree and calculate the new height
        new_root = remove_subtree_and_clone(root, node_to_remove_value)

        height = calculate_tree_height(new_root)
        results.append(height)

    return results

def remove_subtree_and_clone(root, node_to_remove_value):
    if not root:
        return None

    if root.val == node_to_remove_value:
        return None

    new_node = TreeNode(root.val)
    # Recursively build a new tree structure without the specified node.
    new_node.left = remove_subtree_and_clone(root.left, node_to_remove_value)

    new_node.right = remove_subtree_and_clone(root.right, node_to_remove_value)

    return new_node

def calculate_tree_height(root):
    if not root:
        return 0

    # Calculate the height of left and right subtrees.
    left_height = calculate_tree_height(root.left)

    right_height = calculate_tree_height(root.right)

    # Height is the maximum of the two subtrees plus 1 for the current node.
    return max(left_height, right_height) + 1

Big(O) Analysis

Time Complexity

O(n^2) – The algorithm iterates through each of the n queries. For each query (subtree removal), it rebuilds the entire tree, which in the worst case requires visiting all n nodes. After rebuilding the tree for each query, calculating the height of the tree again involves traversing (potentially) all n nodes. Therefore, each of the n queries leads to O(n) work for rebuilding and O(n) work for height calculation so O(n + n) which simplifies to O(n) work. Doing this for each of the n queries results in O(n * n) work which equals O(n^2).

Space Complexity

O(N) – The brute force approach, as described, involves rebuilding the tree after each subtree removal. Rebuilding the tree potentially requires creating a new tree structure, which in the worst case, might have a size similar to the original tree when the removed subtree is small. Additionally, calculating the height of the rebuilt tree will likely involve traversing it which can lead to call stack usage proportional to the height, or an explicit queue if done iteratively. Thus the dominant space complexity factor becomes the potential need to copy the tree, resulting in O(N) auxiliary space, where N is the number of nodes in the original tree.

Optimal Solution

Approach

The core idea is to precompute the height of every node in the tree and then efficiently update heights when a subtree is removed. We need a way to find the next highest path when the current path is removed.

Here's how the algorithm would work step-by-step:

First, calculate and store the height of every node in the entire binary tree. The height of a node is the length of the longest path from that node to a leaf.
Also, store the maximum height from the left and right children of each node separately.
For each query (a node to be removed), simulate removing the subtree rooted at that node.
To figure out the new height of the root of the tree (and all its ancestors), we only need to consider whether removing the specified subtree affected the longest path from the root.
If the removed subtree was part of the longest path from the root, then the new height of the root will be equal to the second longest path (either the height of the other child or zero).
After removing a node, we update the heights of all its ancestors by comparing the heights of their left and right children (excluding what was removed if applicable).
Repeat the process for each query: remove the subtree, adjust affected heights, and output the new height of the root.

Code Implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def height_of_binary_tree_after_subtree_removal_queries(root, queries):
    node_heights = {}
    left_max_heights = {}
    right_max_heights = {}

    def calculate_height(node):
        if not node:
            return -1
        left_height = calculate_height(node.left)
        right_height = calculate_height(node.right)
        node_heights[node] = max(left_height, right_height) + 1
        left_max_heights[node] = left_height
        right_max_heights[node] = right_height
        return node_heights[node]

    calculate_height(root)
    original_root_height = node_heights[root]
    results = []

    for query_node_value in queries:
        query_node = find_node(root, query_node_value)
        
        def calculate_new_height(node, removed_node):
            if node is None:
                return -1
            if node == removed_node:
                return -1

            left_height = calculate_new_height(node.left, removed_node)
            right_height = calculate_new_height(node.right, removed_node)

            return max(left_height, right_height) + 1

        def find_node(node, target):
            if not node:
                return None
            if node.val == target:
                return node
            left_search = find_node(node.left, target)
            if left_search:
                return left_search
            return find_node(node.right, target)

        # Simulate removal by recalculating the root's height
        new_height = calculate_new_height(root, query_node)
        results.append(new_height)

    return results

Big(O) Analysis

Time Complexity

O(n*q) – Calculating the initial height of each of the n nodes in the binary tree takes O(n) time using a recursive depth-first search approach. For each of the q queries, we traverse from the node to be removed up to the root to update the heights of the ancestors. In the worst case, the removed node is a leaf and the tree is skewed, requiring us to update the height of all its ancestors which is at most O(n). Therefore, the time complexity for processing all queries is O(n*q). The initial height calculation is dominated by the query processing, leading to a total time complexity of O(n*q).

Space Complexity

O(N) – The solution stores the height of every node in the binary tree, requiring an auxiliary array (or hash map) of size N, where N is the number of nodes in the tree. Additionally, the solution stores the maximum height from the left and right children of each node, requiring another auxiliary array of size N. The recursion depth for calculating and updating heights could, in the worst-case, reach N. Therefore, the overall auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Null root for the binary tree	Return an empty list as there's no tree to process when root is null.
Empty queries list	Return a list of 0s with the same length as the number of nodes in the tree.
Single node tree and single query that removes that node	Return a list containing only 0, because removing the root leaves an empty tree with height 0.
Complete binary tree with many nodes where each query removes a node on the longest path.	Ensure the height calculation algorithm handles large trees efficiently to avoid timeouts.
Skewed binary tree (left or right leaning) with many nodes.	The algorithm must be able to correctly calculate the height of highly unbalanced trees.
Queries that remove nodes that don't exist in the tree.	The algorithm should ignore these queries and process only valid nodes to remove.
Tree with duplicate values across different subtrees.	The algorithm must correctly identify and remove nodes based on their unique identity, not just their values.
Very deep recursion due to highly unbalanced tree potentially leading to stack overflow.	Consider iterative approaches to avoid excessive recursion depth or using tail-call optimization if the language supports it.

Null root for the binary tree

How to Handle:

Return an empty list as there's no tree to process when root is null.

Empty queries list

How to Handle:

Return a list of 0s with the same length as the number of nodes in the tree.

Single node tree and single query that removes that node

How to Handle:

Return a list containing only 0, because removing the root leaves an empty tree with height 0.

Complete binary tree with many nodes where each query removes a node on the longest path.

How to Handle:

Ensure the height calculation algorithm handles large trees efficiently to avoid timeouts.

Skewed binary tree (left or right leaning) with many nodes.

How to Handle:

The algorithm must be able to correctly calculate the height of highly unbalanced trees.

Queries that remove nodes that don't exist in the tree.

How to Handle:

The algorithm should ignore these queries and process only valid nodes to remove.

Tree with duplicate values across different subtrees.

How to Handle:

The algorithm must correctly identify and remove nodes based on their unique identity, not just their values.

Very deep recursion due to highly unbalanced tree potentially leading to stack overflow.

How to Handle:

Consider iterative approaches to avoid excessive recursion depth or using tail-call optimization if the language supports it.