Easy javascript solutions Beats 100%
Intuition\n\nInitially, I recognized this problem as a tree traversal challenge with a twist. The goal is to find the kth largest perfect subtree sum in a binar
Intuition\n\nInitially, I recognized this problem as a tree traversal challenge with a twist. The goal is to find the kth largest perfect subtree sum in a binary tree. A perfect subtree is a subtree where all nodes have the same number of nodes on the left and right. The key insight is to use a depth-first search (DFS) approach to traverse the tree and calculate subtree sums.\n\nApproach\n\nTo solve this problem, I employed the following steps:\n\n1. Define a MinHeap data structure to store the kth largest perfect subtree sums.\n2. Perform a DFS traversal on the binary tree.\n3. For each node, recursively calculate the subtree sum and check if it\'s perfect.\n4. If the subtree is perfect, add its sum to the MinHeap.\n5. Maintain the MinHeap size to ensure it stores only the kth largest perfect subtree sums.\n6. Return the kth largest perfect subtree sum from the MinHeap.\n\nComplexity\n\n- Time complexity: $$O(n \\log k)$$\n- Space complexity: $$O(k + n)$$\n\nThe time complexity is O(n log k) due to the DFS traversal (O(n)) and maintaining the MinHeap (O(log k)). The space complexity is O(k + n) for storing the MinHeap (O(k)) and recursive call\xA0stack\xA0(O(n)).\n\n# Code\n```javascript []\n\n\n\nclass TreeNode {\n    constructor(val, left = null, right = null) {\n        this.val = val === undefined ? 0 : val;\n        this.left = left === undefined ? null : left;\n        this.right = right === undefined ? null : right;\n    }\n}\n\nclass MinHeap {\n    constructor() {\n        this.heap = [];\n    }\n\n    insert(val) {\n        this.heap.push(val);\n        this.bubbleUp(this.heap.length - 1);\n    }\n\n    extractMin() {\n        if (this.heap.length === 0) return null;\n        if (this.heap.length === 1) return this.heap.pop();\n\n        const min = this.heap[0];\n        this.heap[0] = this.heap.pop();\n        this.bubbleDown(0);\n        return min;\n    }\n\n    peek() {\n        return this.heap[0];\n    }\n\n    getLength() {\n        return this.heap.length;\n    }\n\n    bubbleUp(index) {\n        while (index > 0) {\n            const parentIndex = Math.floor((index - 1) / 2);\n            if (this.heap[parentIndex] <= this.heap[index]) break;\n            [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];\n            index = parentIndex;\n        }\n    }\n\n    bubbleDown(index) {\n        while (true) {\n            const leftChildIndex = 2 * index + 1;\n            const rightChildIndex = 2 * index + 2;\n            let smallest = index;\n\n            if (leftChildIndex < this.heap.length && this.heap[leftChildIndex] < this.heap[smallest]) {\n                smallest = leftChildIndex;\n            }\n\n            if (rightChildIndex < this.heap.length && this.heap[rightChildIndex] < this.heap[smallest]) {\n                smallest = rightChildIndex;\n            }\n\n            if (smallest === index) break;\n            [this.heap[smallest], this.heap[index]] = [this.heap[index], this.heap[smallest]];\n            index = smallest;\n        }\n    }\n\n    remove() {\n        return this.extractMin();\n    }\n}\n\nfunction kthLargestPerfectSubtree(root, k) {\n    const minHeap = new MinHeap();\n\n    function dfs(root, k, minHeap) {\n        if (!root) return [true, 0];\n\n        const [isLeftPerfect, leftCount] = dfs(root.left, k, minHeap);\n        const [isRightPerfect, rightCount] = dfs(root.right, k, minHeap);\n\n        const sum = leftCount + rightCount + 1;\n\n        if (!isLeftPerfect || !isRightPerfect || leftCount !== rightCount) {\n            return [false, sum];\n        }\n\n        if (minHeap.getLength() < k) {\n            minHeap.insert(sum);\n        } else if (sum > minHeap.peek()) {\n            minHeap.remove();\n            minHeap.insert(sum);\n        }\n\n        return [true, sum];\n    }\n\n    dfs(root, k, minHeap);\n\n    return minHeap.getLength() < k ? -1 : minHeap.peek();\n}\n\n\n```
['JavaScript']