Print the nodes having exactly one child in a Binary tree using JavaScript
Given a binary tree, our task is to return the number of nodes in the Binary tree that have at least one child otherwise return “-1” if no such node exists.
Examples:
Input:
1
/ \
2 3
/ \
4 5
/
6
Output: 3
Explanation:
There are three nodes in the Binary tree that have at least one child that are 1,2,4.
Input:
9
/ \
7 8
/ \
4 3
Output: 2
Explanation: There are two nodes in the Binary tree that have
at least one child that are 9,.8
Below are the approaches to return the number of nodes in the Binary tree that have at least one child using JavaScript:
Table of Content
- Using Recursive Depth-First Search (DFS)
- Using Iterative Breadth-First Search (BFS) using Queue
Using Recursive Depth-First Search (DFS)
In this approach, we use recursive depth-first search (DFS) to traverse the binary tree. We start from the root node and recursively visit each node in a depth-first manner. At each node, we check if it has at least one child. If it does, we increment the count. Finally, we return the total count.
Example: The example below shows the program to return the number of nodes in the Binary tree that have at least one child using Recursive Depth-First Search (DFS).
// Definition for a binary tree node.
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
// Function to count nodes with at least
// one child in a binary tree
function countNodesWithChildren(root) {
// Base case: if the node is null, return 0
if (!root) {
return 0;
}
// Recursive DFS traversal
// Count nodes with at least one child
// in the left and right subtrees
let count = countNodesWithChildren(root.left)
+ countNodesWithChildren(root.right);
// If the current node has at least one child,
// increment count
if (root.left || root.right) {
count++;
}
// Return the count
return count;
}
// Example usage:
// Constructing a binary tree
let root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
// Counting nodes with at least one child
let result = countNodesWithChildren(root);
console.log("Number of nodes with at least one child:", result);
Output
Number of nodes with at least one child: 3
Time Complexity: O(N), where N is the number of nodes in the binary tree.
Auxiliary Space: O(H), where H is the height of the binary tree.
Using Iterative Breadth-First Search (BFS) using Queue
In this approach, we use iterative breadth-first search (BFS) with a queue data structure to traverse the binary tree. We start by enqueuing the root node and iteratively dequeue nodes from the queue. At each node, we check if it has at least one child. If it does, we increment the count and enqueue its children if they exist. We continue this process until the queue is empty.
Example: Implementation of a program to return the number of nodes in the Binary tree that have at least one child using Iterative Breadth-First Search (BFS) using Queue.
// Definition for a binary tree node.
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
// Function to count nodes with at least
// one child in a binary tree
function countNodesWithChildren(root) {
// Base case: if the root is null, return 0
if (!root) {
return 0;
}
// Initialize a queue for BFS traversal
let queue = [root];
let count = 0;
// Perform BFS traversal
while (queue.length > 0) {
// Dequeue the front node
let node = queue.shift();
// If the dequeued node has at least one child,
// increment count
if (node.left || node.right) {
count++;
}
// Enqueue left and right children if they exist
if (node.left) {
queue.push(node.left);
}
if (node.right) {
queue.push(node.right);
}
}
// Return the count
return count;
}
// Example usage:
// Constructing a binary tree
let root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
// Counting nodes with at least one child
let result = countNodesWithChildren(root);
console.log("Number of nodes with at least one child:", result);
Output
Number of nodes with at least one child: 3
Time Complexity: O(N), where N is the number of nodes in the binary tree.
Auxiliary Space: O(N), where N is the number of nodes in the binary tree.