Print All Nodes that don't have Sibling

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  
            Addtemp->right node value in store;
        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