Java Segment Tree
The maximum depth after removal of a subtree will be max of depths of all nodes that are not in that subtree\n\nWe find the max by using 2 queries: 1st to find 
The maximum depth after removal of a subtree will be max of depths of all nodes that are not in that subtree\n\nWe find the max by using 2 queries: 1st to find max of depths of all nodes that occur before the current node in preorder traversal and 2nd to find max of depths of all nodes that occur after the subtree in the preorder traversal\n\nThe answer is the max of the results of these queries\n\nIn preorder traversal, each subtree can be represented by a subarray\n\nEg.\n\n![image](https://assets.leetcode.com/users/images/ebdd29e7-4cda-44de-bec9-a0b892704e10_1667114353.8077621.png)\n```\nlet size(x) be size of subtree rooted at x\npreorder = [1, 3, 2, 4, 6, 5, 7]\nsubtree(1) = [1, 3, 2, 4, 6, 5, 7] which is preorder[index(1):index(1)+size(1)]\nsubtree(3) = [3, 2] which is preorder[index(3):index(3)+size(3)]\nsubtree(2) = [2] which is preorder[index(2):index(2)+size(2)]\nsubtree(4) = [4, 6, 5, 7] which is preorder[index(4):index(4)+size(4)]\nsubtree(6) = [6] which is preorder[index(6):index(6)+size(6)]\nsubtree(5) = [5, 7] which is preorder[index(5):index(5)+size(5)]\nsubtree(7) = [7] which is preorder[index(7):index(7)+size(7)]\n```\nSegment tree with range maximum query can be used to find max of any subarray in O(log n)\n<iframe src="https://leetcode.com/playground/AHsCYdo9/shared" frameBorder="0" width="1000" height="1000"></iframe>
['Java']