JavaScript Program to Print all Nodes that do not have any Siblings
Given a Binary Tree, our task is to print all nodes that do not have a sibling (a sibling is a node with the same parent. In a Binary Tree, there can be at most one sibling). The root should not be printed as it cannot have a sibling.
Example:
Input:
Input
Output: 4 5 6
Explanation: As the node 4,5, and 6 has no siblings.
Using Iterative Approach
In this approach we use a queue to perform a The root should not be printed as it (BFS) of the binary tree. I.e. for each node, it checks if the node has only one child. If a node has only one child, that child is added to the result list. After this, the function adds the left and right children of the current node to the queue for further processing.
Example: In this example, we are using the Iterative Approach to print all nodes that do not have any siblings.
// A Binary Tree Node
class Node {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}
// Function to print all nodes
// that do not have siblings
function printSingles(root) {
if (root === null) {
return;
}
let queue = [];
queue.push(root);
while (queue.length > 0) {
let node = queue.shift();
if (node.left !== null && node.right === null) {
console.log(node.left.data);
}
if (node.right !== null && node.left === null) {
console.log(node.right.data);
}
if (node.left !== null) {
queue.push(node.left);
}
if (node.right !== null) {
queue.push(node.right);
}
}
}
// Driver code to test the above function
let root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.right = new Node(4);
root.right.left = new Node(5);
root.right.left.left = new Node(6);
printSingles(root);
Output
4 5 6
Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited once.
Space Complexity: O(N), due to the usage of the queue.
Using Recursive Approach
In this approach, we will use recursion to traverse the binary tree. Here for each node, we check if the node has only one child (either left or right). If a node has only one child, that child is printed. After that, the function recursively calls itself for the left and right children of the current node.
Example: In this example, we are using the recursive approach to print all nodes that do not have any siblings.
// A Binary Tree Node
class Node {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}
// Function to print all nodes
// that do not have siblings
function printSingles(root) {
// Base case
if (root === null) {
return;
}
// If this node has only one child
if (root.left !== null && root.right === null) {
console.log(root.left.data);
printSingles(root.left);
}
if (root.right !== null && root.left === null) {
console.log(root.right.data);
printSingles(root.right);
}
if (root.left !== null && root.right !== null) {
printSingles(root.left);
printSingles(root.right);
}
}
let root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.right = new Node(4);
root.right.left = new Node(5);
root.right.left.left = new Node(6);
printSingles(root);
Output
4 5 6
Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited once.
Space Complexity: O(H), where H is the height of the tree, due to the recursion stack.