1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Iterative Approach
2.1.
Algorithm
2.2.
Implementation in C++
2.2.1.
Time Complexity
2.2.2.
Space Complexity
3.
Space Optimized Approach
3.1.
Algorithm
3.2.
Implementation in C++
3.2.1.
Time Complexity
3.2.2.
Space Complexity
4.
4.1.
What is the traversal of a tree?
4.2.
How many types of traversals are possible in tree data structure?
4.3.
What is a non-linear Data Structure?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Print all nodes that don’t have sibling

Harsh
1 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

## Introduction

A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child in computer science. In this blog, we will discuss a coding problem in which we have to print all nodes that don’t have a sibling. Here, No sibling means that the parent node can only have one child.

### Problem Statement

Given a binary tree, you have to Print all nodes that don't have a sibling ( Two nodes with the same parent are referred to as siblings. There can only be one sibling in a Binary Tree ).

### Sample Examples

Example 1

Input

Output

Explanation

Only node 1 and mode 7 don’t have a sibling.

Example 2

Input

Output

Explanation

Only node 1 and mode 7 don’t have a sibling.

## Iterative Approach

We start at the root and check if the node has one child; if it does, we print the node's only child. If the node has two children, we push both of them in the queue.

### Algorithm

``````ALGORITHM(node):
if node is NULL:
return
create a queue and a vector array
push node into the queue

while queue is not empty do:
temp <- queue.front

if temp->left is not NULL and temp->right is NULL:
push temp->left->data into vector

if temp->left is NULL and temp->right is not NULL:
push temp->right->data into vector

if temp->left is not NULL:
push temp->left into our queue

if temp->right is not NULL:
push temp->rigt into out queue

end

sort the vector array and print it on screen``````

### Implementation in C++

``````#include <bits/stdc++.h>
using namespace std;

// our node
class Node {
public:

int data;
Node* left;
Node* right;

Node(int data){
this->data = data;
left = nullptr;
right = nullptr;
}
};

// Function to print all nodes that dont have a sibling
void printNodes(Node *root)
{

//if root node is null, Return
if (root == nullptr) return;

// queue to store the nodes
queue<Node*> q1;

// pushing root node into the queue
q1.push(root);

// vector to store the answer
vector<int> v;

// While q1 is not empty
while(q1.empty() == false) {
Node *temp = q1.front();
q1.pop();

// checking if the left node is the only child
// if it is, then pushing it into our array
if(temp->left != nullptr && temp->right == nullptr) {
v.push_back(temp->left->data);
}

// checking if the right node is the only child
// if it is, then pushing it into our array
if(temp->left == nullptr && temp->right != nullptr) {
v.push_back(temp->right->data);
}

// if left child is not null
// push it into the queue
if(temp->left != nullptr) {
q1.push(temp->left);
}

// if right child is not null
// push it into the queue
if(temp->right != nullptr) {
q1.push(temp->right);
}
}

// printing result
for (int i = 0; i < v.size(); i++) {
cout<< v[i] << " ";
}

// print -1 if vector is empty
if (v.size() == 0) {
cout<<"-1";
}
}

// main function
int main() {

// creating binary tree
Node *root = new Node(5);
root->left = new Node(9);
root->right = new Node(6);
root->left->left = new Node(1);
root->right->left = new Node(7);

// calling our function
cout << "Nodes without sibling: ";
printNodes(root);
cout << endl;

return 0;
}``````

Output

``Nodes without siblings: 1 7``

#### Time Complexity

We are visiting all the nodes only once. So, The time complexity of our program is O(N). Where N is the number of nodes in the tree.

#### Space Complexity

We are using a queue and vector to store the nodes of the tree. So, the space complexity of our program is O(N) where N is the number of nodes in the 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

## Space Optimized Approach

We start at the root and check if the node has one child; if it does, we print the node's only child. If the node has both children, repeat the process for both of them.

### Algorithm

``````ALGORITHM(node):
If node is NULL:
return
if node->left is not NULL and node->right is NULL:
ALGORITHM(node->left)
ALGORITHM(node->right)
else if node->right is not NULL:
print node->data
ALGORITHM(node->right)
else if node->left is not NULL:
print node->data
ALGORITHM(node->left)``````

### Implementation in C++

``````#include <bits/stdc++.h>
using namespace std;

// our node
class Node {
public:

int data;
Node* left;
Node* right;

Node(int data){
this->data = data;
left = nullptr;
right = nullptr;
}
};

// Function to print all nodes that dont have a sibling
void printNodes(Node *root) {

// if root is null return;
if (root == nullptr) return;

// calling recursion for left and right child
if (root->left != nullptr && root->right != nullptr) {
printNodes(root->left);
printNodes(root->right);
}

// if right child doesn't have a sibling
// print it on screen and recur
else if (root->right != nullptr) {
cout << root->right->data << " ";
printNodes(root->right);
}

// if left child doesn't have a sibling
// print it on screen and recur
else if (root->left != nullptr) {
cout << root->left->data << " ";
printNodes(root->left);
}

}

// main function
int main() {

// creating binary tree
Node *root = new Node(5);
root->left = new Node(9);
root->right = new Node(6);
root->left->left = new Node(1);
root->right->left = new Node(7);

// calling our function
cout << "Nodes without sibling: ";
printNodes(root);
cout << endl;

return 0;
}
``````

Output

``Nodes without siblings: 1 7 ``

#### Time Complexity

We have to visit all the nodes to check whether they have any sibling or not. So, the time complexity of the above program O(n), where n is the number of nodes in our tree.

#### Space Complexity

Constant space is used. So, the space complexity of the above program is O(1).

### What is the traversal of a tree?

Tree traversal (also known as tree search) is a type of graph traversal in computer science that refers to the process of visiting (checking and/or updating) each node in a tree data structure just once. The sequence in which the nodes are visited is used to classify these traversals.

### How many types of traversals are possible in tree data structure?

There are three types of traversal depending on the sequence in which we perform this. Inorder traversal, Preorder traversal and postorder traversal.

### What is a non-linear Data Structure?

A non-linear data structure is one in which data items are not ordered in a logical order; instead, they are put in a random order without forming a linear structure.

Data items can be found at multiple levels, such as a tree.

## Conclusion

In this article, we have extensively discussed a coding problem where we have to print all nodes of a binary tree that don’t have a sibling.

We hope that this blog has helped you enhance your knowledge about the above question and if you would like to learn more, check out our articles Level Order Traversal Of  A Binary TreePrint the node values at odd levels of a Binary treeReplace each node in a binary tree with the sum of its inorder predecessor and successor, and many more on our Website.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Happy Learning!

Live masterclass