We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Height of Binary Tree After Subtree Removal Queries

Difficulty: Hard

Problem Description

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 ith query you 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 ith query.

Key Insights

  • Each query modifies the tree by removing a specific subtree and calculating the height.
  • The height of a tree is defined as the number of edges in the longest simple path from the root to a leaf node.
  • Since the queries are independent, the tree returns to its initial state after each query.
  • Efficient tree traversal and height calculation are critical due to constraints on the number of nodes and queries.

Space and Time Complexity

Time Complexity: O(n) for building the tree and O(m) for processing each query, resulting in O(n + m) overall.

Space Complexity: O(n) for storing the tree structure and auxiliary data structures.

Solution

To solve the problem, we can utilize a Depth-First Search (DFS) or Breadth-First Search (BFS) approach to compute the height of the tree. First, we will build a mapping of each node's children to facilitate quick access when simulating the removal of a subtree. For each query, we will determine the height of the tree by calculating the heights of the remaining children of the root after the specified subtree is removed.

Code Solutions

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

def height_after_removal(root: TreeNode, queries: List[int]) -> List[int]:
    # Function to calculate the height of a tree
    def height(node: TreeNode) -> int:
        if not node:
            return -1  # height of empty tree
        return 1 + max(height(node.left), height(node.right))

    # Build a map from node values to nodes
    node_map = {}
    def build_map(node: TreeNode):
        if not node:
            return
        node_map[node.val] = node
        build_map(node.left)
        build_map(node.right)

    build_map(root)
    answer = []

    for query in queries:
        subtree_root = node_map[query]
        # Calculate the height excluding the subtree
        remaining_height = max(height(root.left), height(root.right))
        # Add the height of the remaining part
        if subtree_root == root.left:
            remaining_height = height(root.right)
        elif subtree_root == root.right:
            remaining_height = height(root.left)
        answer.append(remaining_height)

    return answer
← Back to All Questions