Maximum Perfect Subtree | Dataford Interview Questions

Create a function to find the maximum perfect subtree within a given binary tree. Represent the tree as a level-order list, using None for missing nodes, and return the maximum number of nodes in any perfect subtree. A perfect subtree has two children at every internal node and all leaves at the same depth. For example, [1, 2, 3, 4, 5, 6, 7] returns 7, while [1, 2, 3, 4, 5, 6, None] returns 3.

Constraints

0 <= len(tree) <= 100000
Each non-None entry represents one binary-tree node
The list uses level-order indexing with children at 2i + 1 and 2i + 2
The tree encoding does not contain descendants under a None parent
Return the number of nodes, not the height, of the largest perfect subtree

Function Signature

def max_perfect_subtree(tree):

Your question is Maximum Perfect Subtree. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Constraints

0 <= len(tree) <= 100000
Each non-None entry represents one binary-tree node
The list uses level-order indexing with children at 2i + 1 and 2i + 2
The tree encoding does not contain descendants under a None parent
Return the number of nodes, not the height, of the largest perfect subtree

Function Signature

def max_perfect_subtree(tree):

Your question is Maximum Perfect Subtree. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.