JavaScript Program to Print all Nodes that do not have any Siblings - Coding

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.

JavaScript

// 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.

JavaScript

// 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.

Reffered: https://www.geeksforgeeks.org

JavaScript

Related
Print the nodes having exactly one child in a Binary tree using JavaScript
Moment.js
How to Fix JavaScript TypeError: Cannot Set Properties of Undefined?
Lodash Tutorial
Underscore.js

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	17