Check if a given binary tree is perfect or not in Python

The problem in hand is checking whether a given binary tree is perfect or not.

So, before talking about Perfect binary tress let us first talk about binary trees.

A binary tree is a tree in which each node has at most two children, one left and one right. Some people consider an empty set to be a binary tree as well.

Now let me define what a perfect binary tree is. A binary tree in which all interior nodes have two children and all leaves have the same level or depth is called a perfect binary tree. Example of this type of binary tree is as shown:

A binary tree which is not perfect is as shown:

For writing code, I am using a Python library binarytree. This library is not included in the default setup of Python and the user needs to install it. For installing this library one should use the following command on its system’s cmd prompt.

pip install binarytree

After the library is installed the following code can be used to check whether the given binary tree is perfect or not.

CODE

Now its time to see the code. Below is our Python code to check for whether a given binary tree is perfect or not:

#Python program to check whether a given binary tree is perfect or not
#importing library for forming binary tree
#first install the library using command 'pip install binarytree' in cmd 
from binarytree import Node

#Function to test if binary tree is perfect or not
def perfect(r,depth, l=0):

#If the node is leaf then it's depth must br equal to the depth of all other leaves
    if r.left==None and r.right==None:
        if (depth==l+1):           
            return (True)
        else:
            return (False)

#If node is internal with one empty child
    if r.left==None or r.right==None:
        return False
#Since an empty tree is perfect
    if r==None:
        return True

#Right and left subtrees should be perfect as well
    if (perfect(r.left,depth,l+1) and perfect(r.right,depth,l+1)):
        return(True)
    else:
        return (False)

#Function for finding depth
def Depth(n):
    depth=0
    while(n!= None):
        depth = depth + 1
        n=n.left
    return depth

def Perfect(r):
    depth=Depth(r)
    return perfect(r,depth)
        
#Driver Code
#Declaring root node
r=None
r=Node(15)
#Declaring right and left children of root node
r.left=Node(25)
r.right=Node(35)

#Similarly declaring the rest of the tree
r.left.left=Node(45)
r.left.right= Node(55)
r.right.left= Node(65)
r.right.right= Node(75)

#checking whether the thus formed tree is perfect or not using user defined function and thus printing the result
if (Perfect(r)):
    print("YES, THE FORMED TREE IS PERFECT")
else:
    print("NO, THE FORMED TREE IS NOT PERFECT")

OUTPUT:

YES, THE FORMED TREE IS PERFECT

The time complexity of this code is O(n).

Following are the steps which have been used to write the given code:

First, we find the depth of any node of our choice. In the code given below the depth which I considered is of the leftmost node.
The second step is to traverse the tree recursively and check for the following conditions:
- There should not be any internal node with empty children.
- All leaves must be at depth equal to the depth calculated in the first step.

Check if a given binary tree is perfect or not in Python

CODE

OUTPUT:

Leave a Reply Cancel reply