Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
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.
Frequently Asked Questions
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

Author 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).

Frequently Asked Questions

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!

Previous article
Print all nodes that are at distance k from a leaf node
Next article
Print Ancestors of a Given Node
Live masterclass