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

In this tutorial, we will learn to check whether a binary tree is full or not in the iterative approach in Python. We will be solving the problem in Python. There are many ways of solving this problem; here, I have discussed the iterative approach.

When is a Binary Tree Full?

A binary tree is considered to be full when all the nodes in the tree have either zero or two child nodes. So, we can also say that a full binary tree does not have any nodes with a single leaf. We will travel to each node and look at how many child nodes it has.

The Logic

We will do level order traversal for each node. Then we will check for the following conditions:

If the left and right of the node have null values, that means it is a leaf node. We move forward to the next node.
If any of the left and right of the node does not have null values, that means it has a single child node. We return false and exit the loop.
If the tree is empty, return true.

Finally, we return true if no exception occurs. Since we look at each iteration, this approach is known as the Iterative Approach.

The Iterative Method

Coming to the code, firstly, we declare the Node class.

class Node: 

    def __init__(self, val): 
  self.val = val 
  self.l = None
  self.r = None

Next, check if the tree is empty or not.

if (not root) : 
    return True

Then, create a queue to store the nodes. Check the individual nodes to see whether they are leaf nodes. If so, continue. If they have single child nodes, stop and return false. Otherwise, add the left and right children nodes of the node being traversed. In the end, return true.

que = [] 

    que.append(root) 

    while (not len(que)): 
    
  node = que[0] 
  que.pop(0) 

  if (node.l == None and node.r == None): 
      continue
 
  if (node.l == None or node.r == None): 
      return False

  que.append(node.l) 
        que.append(node.r) 
   
    return True

Finally, make the driver program to check whether the binary tree is full or not.

Iterative: Check whether a binary tree is a full binary tree or not

I have provided the entire code below.

class Node:
    def __init__(self, value):
        self.value = value
        self.l = None
        self.r = None

def status_bin_tree(root):
    if root is None:
        return True

    que = [root]

    while len(que):
        node = que.pop(0)

        if node.l is None and node.r is None:
            continue

        if node.l is None or node.r is None:
            return False

        que.append(node.l)
        que.append(node.r)

    return True

root1 = Node(10)
root1.l = Node(20)
root1.r = Node(30)

root1.l.r = Node(40)
root1.l.l = Node(50)

if status_bin_tree(root1):
    print("The Binary tree is full")
else:
    print("Binary tree is not full")

The output is given below.