# 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

## Leave a Reply