What is a strictly Binary Tree in Data Structures?

There are various kinds of binary trees that we know exist in data structures, and they all have their purposes. In this article, we are going to talk about a specific binary tree named a strictly binary tree. It is the one in which every node present in the tree either contains two nodes or doesn’t have any node at all. They are also popularly known as the full binary tree. In more technical terms, a strictly binary tree which is also known as a full binary tree, tends to be the kind of tree in which all the nodes have their own offspring or children except the leaf nodes.

Here is a strictly binary tree:

How to discover a strictly binary tree?

To find out whether the given binary tree is strictly or not, we have to first check that it must follow all of this properly. The conditions are: -

If we are given a binary tree whose both the subtrees that are left and right are vacant or clear, then there are high chances of it being a strictly binary tree.

If we have a tree whose node is NULL, then it is a strictly binary tree.

If we have a binary tree that already consists of left and right subtrees, then from the definition, we know that it is a strictly binary tree.

In any other way of arrangement of left and right subtrees, it is not a strictly binary tree.

Strictly binary tree theorem: -

Let us suppose that we have a binary tree named M, which is a non-empty tree then: -

Let I be the nodes that are present inside, and L be the leaf nodes that are present in a tree. Then the total number of leaf nodes that are present within a tree can be calculated by: -
L = I + 1

Let us suppose that the tree has M name and if the tree named M has a total number of internal nodes named I and the total number of nodes that are present is to be named N, then the total number of nodes that are present: -
N = 2I + 1

If the tree M has N number of total nodes and I number of internal nodes, then the number of internal nodes that are present in the tree would be calculated by: -
I = (N – 2)/ 2

If we have a tree named M that has a total number of leaf node L and a total number of node N, then the total number of leaf nodes present in the tree will be: -
L = (N + 1)/ 2

If the tree named M has N number of total nodes present within it, then the total number of leaf nodes can be calculated by the given formula: -
N = 2L – 1

If the tree named M has L amount of leaf nodes and I is to be the total number of internal nodes that tree is having, then the total number of internal nodes can be calculated by the given formula: - I = L – 1

Implementation

// Checking if a binary tree is a strictly binary tree in C++


#include <iostream>
using namespace std;


struct Node {
  int key;
  struct Node *left, *right;
};


// New node creation
struct Node *newNode(char k) {
  struct Node *node = (struct Node *)malloc(sizeof(struct Node));
  node->key = k;
  node->right = node->left = NULL;
  return node;
}


bool isStrictlyBinaryTree(struct Node *root) {
  
  // Checking for emptiness
  if (root == NULL)
    return true;


  // Checking for the presence of children
  if (root->left == NULL && root->right == NULL)
    return true;


  if ((root->left) && (root->right))
    return (isStrictlyBinaryTree(root->left) && isStrictlyBinaryTree(root->right));


  return false;
}


int main() {
  struct Node *root = NULL;
  root = newNode(1);
  root->left = newNode(2);
  root->right = newNode(3);
 
root->left->left = newNode(4);
 
root->left->right = newNode(5);
 
root->left->right->left = newNode(6);
 
root->left->right->right = newNode(7);


  if (isStrictlyBinaryTree(root))
    cout << "The tree is a strictly binary tree\n";
  else
    cout << "The tree is not a strictly binary tree\n";
}

Output:

Complexity

In this section, we know about the time and auxiliary space complexity of the strictly binary tree. The time complexity for this kind of tree turns out to be big O of n, which is usually written as O(n), and also the auxiliary space for this kind of tree also turns out to be O(n).

Data Structures Tutorial