Find the Largest Perfect Binary Tree in a Given Tree

A binary tree is generally considered a perfect binary tree when all the nodes present in the binary tree have at least two children and all the leaf nodes are at the same level or stage.

In order to find the giant perfect binary tree, we can use a DFS approach.

1. In this technique, we have to begin from the root of the binary tree.
2. At every given node, we have to ensure that its left and right trees are perfect binary trees.
3. To ensure that each tree is a perfect binary tree, we must observe whether the number of nodes in the subtree is a power of 2. We can do this by counting the number of nodes in any other traversal.
4. If we encounter a subtree that appears to be a perfect binary tree, we have to update the maximum size of the binary tree we have found.
5. We will repeat this process until we have traversed all the nodes in the binary tree.
6. We have to return the size of the perfect binary tree found so far.

Implementation

Output:

A step-by-step explanation of the code

1. Code begins by including the necessary header files, including bits/stdc++.h> containing all standard C++ libraries.
2. Next, we define a structure node in the binary tree which contains various data.
3. We create a function called new node which basically helps us in defining new data, and it also helps us in allocating memory for the nodes and initializing its members.
4. We define another structure whose name is returnType that basically focuses on the type of the perfect binary tree function. It contains three members that are: height, isPerfect, and rootTree.
5. The function findPerfectBinaryTree generally takes a root node as a function and then searches to find the biggest perfect binary tree possible in its range.
6. Inside this function, we first check the base case, which helps us in case we find out that the root is NULL. Then it is considered a perfect binary tree of height 0.
7. If the primary case is not fulfilled, then the functions call out the findPerfectBinaryTree for the current node's left and right child nodes.
8. Next, the result of the left subtree is stored in the lv, and the result of the right subtree is stored in the rv.
9. The functions then verify if both the subtrees are perfect and their heights are the same. If this condition is met, it implies that the current root node is also perfect. In this case, the height of the subtree is set to lv. height + 1, isPerfect is set to true, and the rootTree is set to the current root. We have to wait till the result is returned.
10. If the condition in step 9 is not met, it implies that the current subtree is not perfect.
11. Now, in the program's primary function, we create NewNode to set their left and right pointers.
12. The findPerfectBinaryTree function is called with the root of the binary tree, and the result is stored in the variable named 'ans'.

Example 2)

Output:

A step-by-step explanation of the code

1. The code generally imports the necessary Java util classes in the first step.
2. The code then defines a class named TPT which contains the main logic of the program.
3. Next, the code defines a static nested class called node that represents the node structure of the tree, and each of the nodes comprises an integer value and references to its left and right child.
4. We then move by creating a method called newnode that creates a new node with the given data value, initializing the left and right child node as NULL, and returning the created node.
5. We move by defining another static method named returnType that typically represents the structure of the returnType for the findPerfectBinaryTree function. It mainly comprises three fields: isPerfect, Height, and rootTree.
6. Now, using the method findPerfectBinaryTree, it takes a node object as an input, recursively finds out the biggest binary tree, and returns a returnType that will hold the result.
7. The code will recursively call the findPerfectBinaryTree function for the current node's left and right child nodes.
8. Now the code will verify whether the left and right subtrees are perfect binary trees and have the same height. If this is the case, then the current subtree is also the perfect binary tree, and the function updates the 'rt' object with the height and root data and returns it.
9. In case the current subtree does not turn out to be perfect, then the isPerfect returns the false value. Then we evaluate the maximum height between the left and right subtrees, treat the root of the subtree with the maximum height obtained, and return the 'rt' object.
10. Next, we define another static method called inorder-print that performs the inorder traversal of a binary tree and prints the node values.
11. Finally, the program's primary function is certainly the program's entry point. It typically creates a binary tree with six nodes and assigns it to the root variable. It then conducts all the functions and provides the necessary results.

Conclusion

The above-provided approach is an implementation that finds out the biggest possible perfect binary tree in a given tree. The main conclusion is that the code uses various functions and pointers to efficiently find the possible binary tree and then print its size in the in-order traversal.