answer of size m where answer[i] is the height of the tree after performing the ith 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.

Examples

Example 1:

---
title: Input tree
---
 graph TD;
     A1((1))
     B3((3))
     C4((4)):::query
     D2((2))
     E6((6))
     F5((5))
     G7((7))
     Null3_1(("null")):::null
     Null5_1(("null")):::null
     
     A1 --> B3
     A1 --> C4
     B3 --> D2
     B3 --> Null3_1
     C4 --> E6
     C4 --> F5
     F5 --> Null5_1
     F5 --> G7
     
     classDef query fill:#f96,stroke:#333,stroke-width:4px;
     classDef null fill:#eee,stroke:#999,stroke-width:2px,stroke-dasharray: 5,5;

---
title: Tree after removing query node
---
 graph TD;
     A1((1))
     B3((3))
     D2((2))
     Null1_1(("null")):::null
     Null3_1(("null")):::null
     
     A1 --> B3 & Null1_1
     B3 --> D2 & Null3_1

classDef null fill:#eee,stroke:#999,stroke-width:2px,stroke-dasharray: 5,5;

Input: root = [1,3,4,2,null,6,5,null,null,null,

Related Tags