Check whether a binary tree is a full binary tree or not in Python

In this tutorial, we learn about the Binary tree and how to check whether a given Binary tree is a full Binary tree or not.

Example:
                      1:        (a)               2:        (a)
                              /    \                       /   \
                            (b)    (c)                   null  null
                           /   \ 
                         (d)   (e)

This is a full binary tree becouse here every node has 0 or 2 children by definition. If Binary tree node(head) is NULL 
then it is also a full binary tree by definition.

class Node:
    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data
        
def fullbinarytree(head):
    
    if head is None:
        return True
    
    if head.left is None and head.right is None:
        return True
    
    if head.left is not None and head.right is not None:
        return(fullbinarytree(head.left) and fullbinarytree(head.right))
    
    return False


if __name__ == "__main__":
    
    head = Node('a')
    head.left = Node('b'); 
    head.right = Node('c'); 

    head.left.left = Node('d');
    head.left.right = Node('e');
    
#             (a)
#            /   \
#          (b)   (c)
#         /  \
#      (d)   (e)


    if fullbinarytree(head):
        print("Given Binary is Full Binary tree")
    else:
        print("Given Binary is not Full Binary tree")
    
    

OUTPUT:

Given Binary is Full Binary tree

I hope it helps you. Thanks for visiting codespeedy.

We can also follow this:

Here is a recursive function that takes in a root node of a binary tree and returns True if the tree is a full binary tree, False otherwise:

def is_full_binary_tree(root):
    if root is None:
        return True
    if root.left is None and root.right is None:
        return True
    if root.left is not None and root.right is not None:
        return is_full_binary_tree(root.left) and is_full_binary_tree(root.right)
    return False

This function works by first checking if the root is None, in which case it returns True because an empty tree is considered to be a full binary tree. If the root is not None, it then checks if both the left and right children are None. If they are, then the root is a leaf node and the tree is a full binary tree. If both children are not None, then the function recursively checks if both the left and right subtrees are full binary trees. If they are, then the tree is a full binary tree. If any of these conditions are not met, then the function returns False.

You can use this function by passing in the root node of your binary tree. For example:

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print(is_full_binary_tree(root))  # prints True

Also read:

• How to implement a Binary Tree in Python
• Insertion and Deletion in a Binary search tree in Python
• Find the parent of a node in a binary tree in Python