Standard BFS/DFS approach return and propagate information back upwards O(N) T O(H) Space
Complexity\nLet N := #-nodes in the binary tree\nLet H := height of the binary tree : log2(N) average (N) worst case\n- Time complexity:\nO(N)\n\n- Space comple
# Complexity\nLet N := #-nodes in the binary tree\nLet H := height of the binary tree : log2(N) average (N) worst case\n- Time complexity:\n$$O(N)$$\n\n- Space complexity:\n$$ O(N) ( E ) O(H ) ( I )$$\n\n# Code\n```python3 []\n# Definition for a binary tree node.\n# class TreeNode:\n#     def __init__(self, val=0, left=None, right=None):\n#         self.val = val\n#         self.left = left\n#         self.right = right\n\'\'\'\nURL := https://leetcode.com/problems/k-th-largest-perfect-subtree-size-in-binary-tree/description/\n3319. K-th Largest Perfect Subtree Size in Binary Tree\n\nCategories : Recursion, DP, BFS, DFS, Counting & Enumeration\n\n\nPBT := perfect binary subtree\n2K nodes max decent constraints to the problem @ hand\nHave to get everyone\'s sizes\n\n15 mins to solutioning\n\'\'\'\nclass Solution:\n    def kthLargestPerfectSubtree(self, root: Optional[TreeNode], k: int) -> int:\n        kthSize = -1\n        candidates = []\n        self.dfs(root,candidates)\n        # sort non-decreasing order\n        candidates.sort(key = lambda x : -1 * x)\n        print(candidates)\n        if(k-1 < len(candidates)):\n            kthSize = candidates[k-1]\n        return kthSize\n\n    # return : size of tree, and max level of a leaf, and if it is a perfect tree : 0 = no, 1 = yes\n    def dfs(self,root:TreeNode,candidates:List[int]) -> List[int]:\n        # base case : leaf condition\n        targetRecord = [0,0,0]\n        if(root is None):\n            return targetRecord\n        treeSize = 1\n        if(root.left is None and root.right is None):\n            candidates.append(1)\n            return [1,1,1]\n        elif(root.left is not None and root.right is not None):\n            recordLeft = self.dfs(root.left,candidates)\n            recordRight = self.dfs(root.right,candidates)\n            # both are perfect binary subtrees\n            targetRecord = [0,0,0]\n            if(recordLeft[2] == 1 and recordRight[2] == 1):\n                leafDepthLeft = recordLeft[1]\n                leafDepthRight = recordRight[1]\n                if(leafDepthLeft == leafDepthRight):\n                    treeSize = recordLeft[0] + recordRight[0] + 1\n                    candidates.append(treeSize)\n                    targetRecord = [treeSize,1 + leafDepthLeft,1]\n        else: # single child case : no validity ( perfection ) going upwards too\n            # no validity upwards too :-(\n            recordLeft = self.dfs(root.left,candidates)\n            recordRight = self.dfs(root.right,candidates)\n        return targetRecord\n\n\n    \n\n\n        \n```
['Tree', 'Depth-First Search', 'Sorting', 'Binary Tree', 'Python3']