Python recursion | easy to understand
Intuition\nSince this is a binary tree, I opted to use a recursive function. The key question is, what information about the subtrees of a node do we need to de
# Intuition\nSince this is a binary tree, I opted to use a recursive function. The key question is, what information about the subtrees of a node do we need to determine if a node is perfect.\n\nI used two bits of information: whether the subtrees are perfect, and the heights of those subtrees. A node is perfect **just when** its left and right childs are perfect, and the heights are the same. \n\nWe also need to return the sizes of the nodes in either child that are perfect trees.\n\n# Approach\nSure, I could use quickselect instead of sorting the list. But who really has the time?\n\n# Complexity\n- Time complexity:\nO(n log n)\n\n- Space complexity:\nO(n)\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\nclass Solution:\n    def kthLargestPerfectSubtree(self, root: Optional[TreeNode], k: int) -> int:\n\n        # Returns whether it is a perfect binary tree, the size of the tree, the \n        # sizes of the perfect binary trees and the heights\n        def helper(node):\n            if node is None:\n                return True, [], 0\n\n            left_is_perfect, left_perfects, left_height = helper(node.left)\n            right_is_perfect, right_perfects, right_height = helper(node.right)\n\n            is_perfect = left_is_perfect and right_is_perfect and left_height == right_height\n            height = max(left_height, right_height) + 1\n            perfects = left_perfects + right_perfects\n\n            if is_perfect:\n                perfects.append(2**height-1)\n\n            return is_perfect, perfects, height\n\n        _, perfects, _ = helper(root)\n\n        if k > len(perfects):\n            return -1\n        \n        return sorted(perfects, reverse = True)[k-1]\n```
['Python3']