Home » Interview coding problems/challenges

# 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 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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.

Learn PCB Designing: PCB DESIGNING TUTORIAL