Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in Go

Solution: Height of Binary Tree After Subtree Removal Queries

Explore how to determine the height of a binary tree after removing specified subtrees through depth-first search. Understand how to calculate node depth and height, group nodes by depth, and efficiently answer removal queries to update the tree height. This lesson clarifies a key technique for solving binary tree problems using DFS.

We'll cover the following...

Statement

We are given the root of a binary tree with nn nodes and an array, queries, of size mm. Each query represents the root of a subtree that should be removed from the tree. The task here is to determine the height of the binary tree after each query, i.e., once a subtree is removed. We'll store the updated heights against each query in an array and return it.

Note: A tree’s height is the number of edges in the longest path from the root to any leaf node in the tree.

A few points to be considered:

  • All the values in the tree are unique.

  • It is guaranteed that queries[i] ...