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 screenImplementation 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.
519+ registered 
