# Print All Nodes that don't have Sibling

In this article, we are going to see how to find the nodes that have no siblings? This problem has been featured in the coding round of D.E. Shaw, Amazon.
Submitted by Radib Kar, on December 17, 2018

Problem Statement:

Given a Binary Tree write a program to print the nodes which don’t have a sibling node. Print all the nodes separated by space which don't have sibling in the tree in sorted order if every node has a tree than print -1. Explanation with example:

What is having sibling in tree?

A child node is said to have a sibling if the other node has the same parent as the child node. That means the nodes are siblings if they have same parent.

Like in the above example ‘2’ & ‘6’ are siblings as they have the same parent ‘7’.

In the above example the nodes that don’t have siblings are: 9, 4

Thus output:

4, 9 (sorted)

N.B: Root is not considered for sibling checking.

Solution:

So, clearly a child node don’t have sibling, if its parent has only one pointer, either left or the right (that’s the child of course). Then we simply store the child node value & produce a sorted list to print. The traversal method we use here is level order traversal.

Algorithm:

```1. Define tree Node structure
2. FUNCTION printSibling (Node* root)
a) Declare a queue& a vector using STL
Queue<Node*>q;
vector<int>store;
b) push the root
EnQueue(q,root);
Node* temp;
While(queue is not empty) //do the level order traversal & check for siblings
temp=DeQueue(q);
//if the current node has only one child, definitely the child
//has no sibling, thus store the child node value
//left child pointer in NULL, right is not
If temp->left==NULL&&temp->right!=NULL
END IF
//right child pointer in NULL, left is not
If temp->left!=NULL&&temp->right==NULL
Add temp->left node value in store;
END IF
// do level order traversing
IF(temp->right)
EnQueue(q, temp->right);
IF(temp->left)
EnQueue(q, temp->left);
END WHILE
c) If no node found without having sibling then vector size is zero then print -1
d) Elsesort the vector to print sorted node value
END FUNCTION
```

## C++ implementation to Print All Nodes that don't have Sibling

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

// tree node is defined
class tree{
public:
int data;
tree *left;
tree *right;
};

void printSibling(tree* root)
{
//Declare queue using STL
queue<tree*> q;
//enqueue the root
q.push(root);
vector<int> store;

tree* temp;
//do the level order traversal & check for siblings
while(!q.empty()){
//dequeue
temp=q.front();
q.pop();
//if the current node has only one child
//definitely the child has no sibling
//store the child node value
if(temp->left==NULL && temp->right!=NULL){
store.push_back(temp->right->data);
}

if(temp->left!=NULL && temp->right==NULL){
store.push_back(temp->left->data);
}
// do level order traversing
if(temp->right)
q.push(temp->right);
if(temp->left)
q.push(temp->left);
}
//if no node found without having sibling
//vector size is zero
//print -1
if(store.size()==0){
printf("-1, no such  node\n");
return;
}
//sort the vector to print sorted node value
sort(store.begin(),store.end());
//printing
for(auto it=store.begin();it!=store.end();it++)
printf("%d ",*it);
}

tree* newnode(int data)  // creating new node
{
tree* node = (tree*)malloc(sizeof(tree));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

int main()
{
//**same tree is builted as shown in example**
cout<<"same tree is built as shown in example\n";
tree *root=newnode(2);
root->left= newnode(7);
root->right= newnode(5);
root->right->right=newnode(9);
root->right->right->left=newnode(4);
root->left->left=newnode(2);
root->left->right=newnode(6);
root->left->right->left=newnode(5);
root->left->right->right=newnode(11);

cout<<"printing the nodes that don't have sibling...\n"<<endl;
printSibling(root);

return 0;
}
```

Output

```same tree is built as shown in example
printing the nodes that don't have sibling...

4 9
```

TOP Interview Coding Problems/Challenges

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates