Java | Custom Tree Node + Height impact
Intuition\nFirst of all we are going to created a CustomTreeNode that will add the following data for every tree node:\n Parent pointer\n Right subtree height\n
# Intuition\nFirst of all we are going to created a `CustomTreeNode` that will add the following data for every tree node:\n* Parent pointer\n* Right subtree height\n* Left subtree height\n\nWe are also going to create a `Map<Integer, CustomTreeNode>` so we can get direct access of the deleted node.\n\nFrom here we are going to traverse upwards and check if by deleting the current node we impacted the parent node maximum height. If we did, we calculate the `deltaOfDeletion` which is basically a number representing how much of the max-height to remove from the next parent.\n\nWe do this the whole way up the tree (we have reference to parents) and get the root node height.\n\n# Code\n```\nclass Solution {\n    Map<Integer, CustomTreeNode> valToCustomNode = new HashMap<>();\n\n    public int[] treeQueries(TreeNode root, int[] queries) {\n        CustomTreeNode customRoot = buildCustomTree(null, root); // also sets valToCustomNode - side effect for efficiency\n        setNodeHeights(customRoot);\n        int m = queries.length;\n        int[] res = new int[m];\n\n        for (int i = 0; i < m; i++) {\n            int query = queries[i];\n\n            CustomTreeNode impactedNode = valToCustomNode.get(query);\n            int deltaOfDeletion = impactedNode.treeHeight();\n\n            while (impactedNode.parent != null) {\n                CustomTreeNode parent = impactedNode.parent;\n                int curNewMaxHeight = 0;\n\n\t\t\t\t// Indicates impactedNode is the *right* node of parent\n                if (parent.right != null && parent.right.val == impactedNode.val) {\n                    int newRightHeight = parent.rightTreeHeight - deltaOfDeletion;\n                    curNewMaxHeight = Math.max(parent.leftTreeHeight, newRightHeight);\n\n\t\t\t\t// Indicates impactedNode is the *left* node of parent\n                } else {\n                    int newLeftHeight = parent.leftTreeHeight - deltaOfDeletion;\n                    curNewMaxHeight = Math.max(newLeftHeight, parent.rightTreeHeight);\n                }\n\n                deltaOfDeletion = parent.treeHeight() - curNewMaxHeight;\n                impactedNode = parent;\n\t\n\t\t\t\t// There is no more impact to the deletion. (example: deleted left subtree but right subtree was bigger)\n                if (deltaOfDeletion == 0) break; // Optimization\n            }\n\n            res[i] = customRoot.treeHeight() - deltaOfDeletion - 1;\n\n        }\n\n        return res;\n    }\n\n    private CustomTreeNode buildCustomTree(CustomTreeNode parent, TreeNode root) {\n        if (root == null) return null;\n\n        CustomTreeNode node = new CustomTreeNode(root.val, parent);\n        node.setRightTree(buildCustomTree(node, root.right));\n        node.setLeftTree(buildCustomTree(node, root.left));\n        valToCustomNode.put(node.val, node);\n\n        return node;\n    }\n\n    private int setNodeHeights(CustomTreeNode node) {\n        if (node == null) return 0;\n\n        int leftNodeHeight = setNodeHeights(node.left);\n        int rightNodeHeight = setNodeHeights(node.right);\n        node.leftTreeHeight = 1 + leftNodeHeight;\n        node.rightTreeHeight = 1 + rightNodeHeight;\n        return node.treeHeight();\n\n    }\n\n\n    class CustomTreeNode {\n        public int val;\n        public CustomTreeNode parent;\n        public CustomTreeNode left;\n        public CustomTreeNode right;\n        public int leftTreeHeight;\n        public int rightTreeHeight;\n\n        public CustomTreeNode(int val, CustomTreeNode parent) {\n            this.val = val;\n            this.parent = parent;\n        }\n\n        public void setRightTree(CustomTreeNode rightNode) {\n            this.right = rightNode;\n        }\n\n        public void setLeftTree(CustomTreeNode leftNode) {\n            this.left = leftNode;\n        }\n\n        public int treeHeight() {\n            return Math.max(leftTreeHeight, rightTreeHeight);\n        }\n\n        @Override\n        public String toString() {\n            return "CustomTreeNode{" +\n                    "val=" + val +\n                    ", leftTreeHeight=" + leftTreeHeight +\n                    ", rightTreeHeight=" + rightTreeHeight +\n                    \'}\';\n        }\n    }\n}\n```\n\n# Complexity\nm - queries\nn - number of nodes\n\nAverage case - `m * log(n)`\nWorst case - `m * n`
['Java']