**π‘ Problem Formulation:** In the realm of binary trees, a perfect subtree is a subtrees that is both full and complete, meaning all its internal nodes have two children and all leaves are at the same depth. The challenge is to find the largest such subtree within a given binary tree. For instance, if we input a binary tree with varying levels of completeness, we want to output the root node and the size of its largest perfect subtree.

## Method 1: Recursive Depth Counting

This approach uses a recursive function to count the depth of the left and right children of a binary tree. If the depths are equal, it implies the subtree rooted at that node is perfect. Function specification involves calculating the depth of subtrees and returning the maximum size of a perfect subtree found.

Here’s an example:

class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def findLargestPerfectSubtree(root): def isPerfect(node): if not node: return 0 left_depth = isPerfect(node.left) right_depth = isPerfect(node.right) if left_depth == right_depth: return left_depth + 1 return 0 if not root: return 0 return max(isPerfect(root), findLargestPerfectSubtree(root.left), findLargestPerfectSubtree(root.right)) # Example binary tree root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(7))) print(findLargestPerfectSubtree(root))

Output: 2

This code defines a TreeNode to construct the binary tree and a recursive function to compute the largest perfect subtree. The `isPerfect`

helper function returns the depth of perfect subtrees or 0 otherwise. The main function compares the size of the perfect subtrees found in the current root and its left and right children recursively.

## Method 2: Bottom-Up Recursive Approach

A bottom-up recursion checks from the leaves upwards to identify perfect subtrees, returning both the depth and validity of a subtree. This reduces redundant checks on nodes that have already been evaluated.

Here’s an example:

def findLargestPerfectSubtreeBottomUp(root): def checkSubtree(node): if not node: return 0, True left_depth, is_left_perfect = checkSubtree(node.left) right_depth, is_right_perfect = checkSubtree(node.right) if is_left_perfect and is_right_perfect and left_depth == right_depth: return left_depth + 1, True return max(left_depth, right_depth), False max_depth, _ = checkSubtree(root) return max_depth print(findLargestPerfectSubtreeBottomUp(root))

Output: 2

In this method, `checkSubtree`

function returns a tuple containing the depth and a boolean flag that indicates if the subtree is perfect. The main function `findLargestPerfectSubtreeBottomUp`

calls `checkSubtree`

and extracts the maximum depth recorded from a perfect subtree.

## Method 3: Level Order Traversal

By traversing the tree level by level, one can detect when a level is not completely filled, which signifies the end of a perfect subtree. This method uses a queue to implement a breadth-first search.

Here’s an example:

from collections import deque def findLargestPerfectSubtreeLevelOrder(root): if not root: return 0 queue = deque([(root, 1)]) perfect_depth = 0 while queue: node, depth = queue.popleft() if node.left and node.right: queue.append((node.left, depth + 1)) queue.append((node.right, depth + 1)) perfect_depth = depth else: break return perfect_depth print(findLargestPerfectSubtreeLevelOrder(root))

Output: 2

This code uses a queue to implement a level order traversal. Nodes along with their depths are added to the queue. If both children are present, the perfect depth is updated; otherwise, it indicates an imperfect level, and the traversal ends.

## Method 4: Optimized Space Usage

This variant of the depth counting method aims to save space by using a single variable to track the maximum perfect subtree depth encountered during traversal.

Here’s an example:

def findLargestPerfectSubtreeOptimized(root): max_perfect_depth = 0 def checkSubtree(node, depth): nonlocal max_perfect_depth if not node: return depth left_depth = checkSubtree(node.left, depth + 1) right_depth = checkSubtree(node.right, depth + 1) if left_depth == right_depth: max_perfect_depth = max(max_perfect_depth, left_depth) return max(left_depth, right_depth) checkSubtree(root, 0) return max_perfect_depth print(findLargestPerfectSubtreeOptimized(root))

Output: 2

In this method, a helper function `checkSubtree`

is called recursively. It returns the depth of the subtree, updating a nonlocal variable `max_perfect_depth`

when a perfect subtree is detected at the current node level.

## Bonus One-Liner Method 5: Recursion with Built-in Maximum Function

The Python one-liner takes advantage of the built-in `max()`

function to condense the recursive approach into a single return statement.

Here’s an example:

def findLargestPerfectSubtreeOneLiner(root): return max(isPerfect(root), findLargestPerfectSubtree(root.left), findLargestPerfectSubtree(root.right)) if root else 0 # Assuming `isPerfect` function is already defined as in Method 1. print(findLargestPerfectSubtreeOneLiner(root))

Output: 2

This concise one-liner combines a check for the root being `None`

and calls to the recursive isPerfect function on the left and right children using the `max()`

function.

## Summary/Discussion

**Method 1:**Recursive Depth Counting. Intuitive approach but may lead to redundant checks. Efficient with balanced trees.**Method 2:**Bottom-Up Recursive Approach. Optimizes by eliminating redundant subtree depth calculations. More complex to understand but efficient in all cases.**Method 3:**Level Order Traversal. Easy to visualize and implement, but can be inefficient due to queue operations for large trees.**Method 4:**Optimized Space Usage. Reduces space complexity but may still perform redundant operations for imbalanced trees.**Method 5:**Recursion with Built-in Maximum Function. Elegantly simple, yet abstracts away from the actual processing logic making it less instructive.