💡 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.