Data Structures Tutorial

Data Structures Tutorial Asymptotic Notation Structure and Union Array Data Structure Linked list Data Structure Type of Linked list Advantages and Disadvantages of linked list Queue Data Structure Implementation of Queue Stack Data Structure Implementation of Stack Sorting Insertion sort Quick sort Selection sort Heap sort Merge sort Bucket sort Count sort Radix sort Shell sort Tree Traversal of the binary tree Binary search tree Graph Spanning tree Linear Search Binary Search Hashing Collision Resolution Techniques

Misc Topic:

Priority Queue in Data Structure Deque in Data Structure Difference Between Linear And Non Linear Data Structures Queue Operations In Data Structure About Data Structures Data Structures Algorithms Types of Data Structures Big O Notations Introduction to Arrays Introduction to 1D-Arrays Operations on 1D-Arrays Introduction to 2D-Arrays Operations on 2D-Arrays Strings in Data Structures String Operations Application of 2D array Bubble Sort Insertion Sort Sorting Algorithms What is DFS Algorithm What Is Graph Data Structure What is the difference between Tree and Graph What is the difference between DFS and BFS Bucket Sort Dijkstra’s vs Bellman-Ford Algorithm Linear Queue Data Structure in C Stack Using Array Stack Using Linked List Recursion in Fibonacci Stack vs Array What is Skewed Binary Tree Primitive Data Structure in C Dynamic memory allocation of structure in C Application of Stack in Data Structures Binary Tree in Data Structures Heap Data Structure Recursion - Factorial and Fibonacci What is B tree what is B+ tree Huffman tree in Data Structures Insertion Sort vs Bubble Sort Adding one to the number represented an array of digits Bitwise Operators and their Important Tricks Blowfish algorithm Bubble Sort vs Selection Sort Hashing and its Applications Heap Sort vs Merge Sort Insertion Sort vs Selection Sort Merge Conflicts and ways to handle them Difference between Stack and Queue AVL tree in data structure c++ Bubble sort algorithm using Javascript Buffer overflow attack with examples Find out the area between two concentric circles Lowest common ancestor in a binary search tree Number of visible boxes putting one inside another Program to calculate the area of the circumcircle of an equilateral triangle Red-black Tree in Data Structures Strictly binary tree in Data Structures 2-3 Trees and Basic Operations on them Asynchronous advantage actor-critic (A3C) Algorithm Bubble Sort vs Heap Sort Digital Search Tree in Data Structures Minimum Spanning Tree Permutation Sort or Bogo Sort Quick Sort vs Merge Sort Boruvkas algorithm Bubble Sort vs Quick Sort Common Operations on various Data Structures Detect and Remove Loop in a Linked List How to Start Learning DSA Print kth least significant bit number Why is Binary Heap Preferred over BST for Priority Queue Bin Packing Problem Binary Tree Inorder Traversal Burning binary tree Equal Sum What is a Threaded Binary Tree? What is a full Binary Tree? Bubble Sort vs Merge Sort B+ Tree Program in Q language Deletion Operation from A B Tree Deletion Operation of the binary search tree in C++ language Does Overloading Work with Inheritance Balanced Binary Tree Binary tree deletion Binary tree insertion Cocktail Sort Comb Sort FIFO approach Operations of B Tree in C++ Language Recaman’s Sequence Tim Sort Understanding Data Processing

Strictly binary tree in Data Structures?

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: -

  1. 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.
  1. If we have a tree whose node is NULL, then it is a strictly binary tree.
  1. 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.
  1. 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:

Strictly Binary Tree

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).



ADVERTISEMENT
ADVERTISEMENT