Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Approach
2.1.
Algorithm
2.2.
Implementation
2.2.1.
Complexity Analysis
3.
Frequently Asked Questions
3.1.
Is it possible for a binary tree to be empty?
3.2.
What do you mean by a degenerate binary tree?
3.3.
When is a binary tree called a strict binary tree?
3.4.
What is a rooted binary tree, and how does it work?
4.
Conclusion
Last Updated: Mar 27, 2024
Easy

Print all full nodes in a Binary Tree

Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

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;
}

 

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.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

Is it possible for a binary tree to be empty?

A binary tree(mutable) can be in either an empty or non-empty state. It contains no data when it is empty. It includes a root element and two different data elements called the left and right subtree when it is not empty.

What do you mean by a degenerate binary tree?

A Degenerate Binary Tree is a Binary Tree with only one child node for each parent node.

One interesting fact about the degenerate binary trees is that the total number of nodes in a Degenerate Binary Tree equals its height.

When is a binary tree called a strict binary tree?

2n -1 nodes are always present in a strictly binary tree with n leaves. A binary tree is strictly binary if every non-leaf node contains nonempty left and right subtrees. To put it another way, in a strictly binary tree, all nodes are of degree zero or two, never one.

What is a rooted binary tree, and how does it work?

A binary tree is a rooted and ordered tree (also known as a plane tree) in which each node has no more than two children. Because a rooted tree naturally brings a sense of levels (distance from the root), each node's children can be described as nodes connected to it at a lower level.

Conclusion

This article ran through a DSA problem to print all full nodes in a binary tree. 

We have discussed:

  • Problem statement to print all full nodes in a binary tree.
  • Example of the given problem to print all full nodes in a binary tree.
  • Algorithm to print all full nodes in a binary tree.
  • Implementation of the Algorithm.

 

We hope this article helped you increase your knowledge of the binary tree. This article is related to the binary tree, so it is recommended to visit our curated section of Binary trees at the Coding Ninjas Studio library, where you can learn Binary tree traversalsTypes of Binary treesvarious operations on a binary tree, and different problems related to binary tree.

You can also visit our curated sections of BSTAVL treeGraphTrieDynamic programming, and many more.

Recommended problems -

 

Head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, interview bundle, follow guided paths for placement preparations, and much more!!

We wish you Good Luck! Keep coding and keep reading Ninja!!

Previous article
Print all root leaf paths with their relative positions
Next article
Print All Leaf Nodes of a Binary Tree from Left to Right
Live masterclass