Note that the values contained in the nodes are not relevant in this task.
A binary tree is called perfect if all of its nodes have exactly 0 or 2 children and all of its leaves are at the same level. By the size of a perfect tree we mean its number of nodes.
Example of a perfect tree of size 7: see image.
Your task is to calculate the size of the biggest perfect subtree that can be obtained by removing any number of nodes.
Consider the following binary tree: see image.
After removing nodes 1, 2, 4, and 11 you obtain a perfect tree of size 7 (as shown by the green nodes). Perfect trees of size 3 are rooted at: 1, 3, 5 and 6, but they are obviously smaller than the best answer of 7.
Write a function:
class Solution { public int solution(Tree T); }
that, given a non-empty binary tree T consisting of N nodes, returns the size of the biggest perfect subtree that can be obtained by removing nodes. For example, given tree T as shown in the previous figure, the function should return 7, as explained above.
Write an efficient algorithm for the following assumptions:
A binary tree can be specified using a pointer data structure. Assume that the following declarations are given:
class Tree {
public int x;
public Tree l;
public Tree r;
};
An empty tree is represented by an empty pointer (denoted by null). A non-empty tree is represented by a pointer on an object representing its root. The attribute x holds the integer contained in the root, wherease attributes l and r hold the left and right subtrees of the binary tree, respectively.
For the purpose of entering your own test cases, you can denote a tree recursively in the following way. An empty binary tree is denoted by None. A none-empty tree is denoted as (X, L, R), where X is the value contained in the root and L and R denote the left and right subtrees, respectively. The tree from the above figure can be denoted as:
(1, (2, None, (4, None, Nonee)), (3, (5, (7, None, None), (8, None, None)), (6, (9, None, None), (10, (11, None, None), None))))