Print all full nodes in a Binary Tree

Introduction

Binary Trees are one of the most commonly utilised Tree Data Structures in real-world software systems. Do you know how vital this data structure is?

The binary tree is the default data structure in Microsoft Excel and spreadsheets. The indexing of a Segmented Database is also implemented using a Binary Tree. The DNS(Domain Name System) also uses Binary trees and many more!! Isn’t it amazing??

So, Let’s discuss one of the problems related to the Binary Tree. This article will discuss how to print all full nodes in a Binary Tree.

Problem Statement

A binary tree is a non-linear data structure in which each node represents an element with some value and no more than two child nodes. In a binary tree, the full nodes are those nodes in the tree that have both children.

Ninja is fascinated by Binary Trees. Given a binary tree, he wonders what the number of full nodes would be in that binary tree.

Help Ninja to print all the full nodes in a binary tree.

Sample Examples

Here are a few examples of the input and output of our problem to print all full nodes in a binary tree.

Input:

Output:

5  8

Input:

Output:

9  2

Approach

The approach is quite simple. We must traverse the tree to print all full nodes in a binary tree.

Algorithm

1. Traverse the binary tree using any of the following traversals in a binary tree
   • Inorder Traversal
   • Preorder Traversal
   • Postorder Traversal
   • Level Order  Traversal
      
2. Check if the node has a left and right child during traversal.
    
3. And if so, print it.

Implementation

It’s time to see the implementation part to print all full nodes in a binary tree. The given code is the implementation of our algorithm in C++ language.

#include <iostream>
using namespace std;

struct Nodes
{
  int data;
  struct Nodes *left, *right;
};


Nodes *insertNewNode(int data)
{
  Nodes *tmp = new Nodes;
  tmp->data = data;
  tmp->left = tmp->right = NULL;
  return tmp;
}


// Traverses the given binary tree 


void findFullNodes(Nodes *root)
{
   if (root != NULL)
  {
      findFullNodes(root->left);
      if (root->left != NULL && root->right != NULL)
      cout << root->data << " ";
      findFullNodes(root->right);
   }
}


// Driver Code
int main()
{
   Nodes* root = insertNewNode(10);
   root->left = insertNewNode(12);
   root->right = insertNewNode(23);
   root->left->left = insertNewNode(14);
   root->right->left = insertNewNode(25);
   root->right->right = insertNewNode(16);
   root->right->left->right = insertNewNode(27);
   root->right->right->right = insertNewNode(28);
   root->right->left->right->left = insertNewNode(19);

   cout<<"All the full nodes of the given binary tree are :\n";
   findFullNodes(root);
   return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Complexity Analysis

• Time Complexity: O(n), The time complexity for our recursive solution to print all full nodes in a binary tree is O(n) in traversing the complete binary tree.
   
• Space Complexity: O(n) for the stack space in our recursive solution to print all full nodes in a binary tree.