Count of nodes in a Binary tree with immediate children as its factors
Given a Binary Tree, the task is to print the count of nodes whose immediate children are its factors.
Examples:
Input:
1
/ \
15 20
/ \ / \
3 5 4 2
\ /
2 3
Output: 2
Explanation:
Children of 15 (3, 5)
are factors of 15
Children of 20 (4, 2)
are factors of 20
Input:
7
/ \
210 14
/ \ \
70 14 30
/ \ / \
2 5 10 15
/
23
Output:3
Explanation:
Children of 210 (70, 14)
are factors of 210
Children of 70 (2, 5)
are factors of 70
Children of 30 (10, 15)
are factors of 30
Approach: In order to solve this problem, we need to traverse the given Binary Tree in Level Order fashion and for every node with both children, check if both the children have values which are factors of the value of the current node. If true, then count such nodes and print it at the end.
Below is the implementation of the above approach:
C++
// C++ program for Counting nodes// whose immediate children// are its factors#include <bits/stdc++.h>using namespace std;// A Tree nodestruct Node { int key; struct Node *left, *right;};// Utility function to create a new nodeNode* newNode(int key){ Node* temp = new Node; temp->key = key; temp->left = temp->right = NULL; return (temp);}// Function to check and print if// immediate children of a node// are its factors or notbool areChilrenFactors( struct Node* parent, struct Node* a, struct Node* b){ if (parent->key % a->key == 0 && parent->key % b->key == 0) return true; else return false;}// Function to get the// count of full Nodes in// a binary treeunsigned int getCount(struct Node* node){ // If tree is empty if (!node) return 0; queue<Node*> q; // Do level order traversal // starting from root int count = 0; // Store the number of nodes // with both children as factors q.push(node); while (!q.empty()) { struct Node* temp = q.front(); q.pop(); if (temp->left && temp->right) { if (areChilrenFactors( temp, temp->left, temp->right)) count++; } if (temp->left != NULL) q.push(temp->left); if (temp->right != NULL) q.push(temp->right); } return count;}// Function to find total no of nodes// In a given binary treeint findSize(struct Node* node){ // Base condition if (node == NULL) return 0; return 1 + findSize(node->left) + findSize(node->right);}// Driver Codeint main(){ /* 10 / \ 40 36 / \ 18 12 / \ / \ 2 6 3 4 / 7 */ // Create Binary Tree as shown Node* root = newNode(10); root->left = newNode(40); root->right = newNode(36); root->right->left = newNode(18); root->right->right = newNode(12); root->right->left->left = newNode(2); root->right->left->right = newNode(6); root->right->right->left = newNode(3); root->right->right->right = newNode(4); root->right->right->right->left = newNode(7); // Print all nodes having // children as their factors cout << getCount(root) << endl; return 0;} |
Java
// Java program for Counting nodes// whose immediate children// are its factors import java.util.*;class GFG{ // A Tree nodestatic class Node { int key; Node left, right;}; // Utility function to create a new nodestatic Node newNode(int key){ Node temp = new Node(); temp.key = key; temp.left = temp.right = null; return (temp);} // Function to check and print if// immediate children of a node// are its factors or notstatic boolean areChilrenFactors( Node parent, Node a, Node b){ if (parent.key % a.key == 0 && parent.key % b.key == 0) return true; else return false;} // Function to get the// count of full Nodes in// a binary treestatic int getCount(Node node){ // If tree is empty if (node==null) return 0; Queue<Node> q = new LinkedList<Node>(); // Do level order traversal // starting from root int count = 0; // Store the number of nodes // with both children as factors q.add(node); while (!q.isEmpty()) { Node temp = q.peek(); q.remove(); if (temp.left!=null && temp.right!=null) { if (areChilrenFactors( temp, temp.left, temp.right)) count++; } if (temp.left != null) q.add(temp.left); if (temp.right != null) q.add(temp.right); } return count;} // Function to find total no of nodes// In a given binary treestatic int findSize(Node node){ // Base condition if (node == null) return 0; return 1 + findSize(node.left) + findSize(node.right);} // Driver Codepublic static void main(String[] args){ /* 10 / \ 40 36 / \ 18 12 / \ / \ 2 6 3 4 / 7 */ // Create Binary Tree as shown Node root = newNode(10); root.left = newNode(40); root.right = newNode(36); root.right.left = newNode(18); root.right.right = newNode(12); root.right.left.left = newNode(2); root.right.left.right = newNode(6); root.right.right.left = newNode(3); root.right.right.right = newNode(4); root.right.right.right.left = newNode(7); // Print all nodes having // children as their factors System.out.print(getCount(root) +"\n"); }}// This code is contributed by sapnasingh4991 |
Python3
# Python3 program for counting nodes# whose immediate children# are its factorsfrom collections import deque as queue# A Binary Tree Nodeclass Node: def __init__(self, key): self.data = key self.left = None self.right = None# Function to check and print if# immediate children of a node# are its factors or notdef areChildrenFactors(parent, a, b): if (parent.data % a.data == 0 and parent.data % b.data == 0): return True else: return False# Function to get the# count of full Nodes in# a binary treedef getCount(node): # Base Case if (not node): return 0 q = queue() # Do level order traversal # starting from root count = 0 # Store the number of nodes # with both children as factors q.append(node) while (len(q) > 0): temp = q.popleft() #q.pop() if (temp.left and temp.right): if (areChildrenFactors(temp, temp.left, temp.right)): count += 1 if (temp.left != None): q.append(temp.left) if (temp.right != None): q.append(temp.right) return count# Function to find total# number of nodes# In a given binary treedef findSize(node): # Base condition if (node == None): return 0 return (1 + findSize(node.left) + findSize(node.right))# Driver Codeif __name__ == '__main__': # /* 10 # / \ # 40 36 # / \ # 18 12 # / \ / \ # 2 6 3 4 # / # 7 # */ # Create Binary Tree root = Node(10) root.left = Node(40) root.right = Node(36) root.right.left = Node(18) root.right.right = Node(12) root.right.left.left = Node(2) root.right.left.right = Node(6) root.right.right.left = Node(3) root.right.right.right = Node(4) root.right.right.right.left = Node(7) # Print all nodes having # children as their factors print(getCount(root))# This code is contributed by mohit kumar 29 |
C#
// C# program for Counting nodes// whose immediate children// are its factorsusing System;using System.Collections.Generic;class GFG{ // A Tree nodeclass Node { public int key; public Node left, right;}; // Utility function to create a new nodestatic Node newNode(int key){ Node temp = new Node(); temp.key = key; temp.left = temp.right = null; return (temp);} // Function to check and print if// immediate children of a node// are its factors or notstatic bool areChilrenFactors( Node parent, Node a, Node b){ if (parent.key % a.key == 0 && parent.key % b.key == 0) return true; else return false;} // Function to get the// count of full Nodes in// a binary treestatic int getCount(Node node){ // If tree is empty if (node == null) return 0; List<Node> q = new List<Node>(); // Do level order traversal // starting from root int count = 0; // Store the number of nodes // with both children as factors q.Add(node); while (q.Count != 0) { Node temp = q[0]; q.RemoveAt(0); if (temp.left!=null && temp.right != null) { if (areChilrenFactors( temp, temp.left, temp.right)) count++; } if (temp.left != null) q.Add(temp.left); if (temp.right != null) q.Add(temp.right); } return count;} // Function to find total no of nodes// In a given binary treestatic int findSize(Node node){ // Base condition if (node == null) return 0; return 1 + findSize(node.left) + findSize(node.right);} // Driver Codepublic static void Main(String[] args){ /* 10 / \ 40 36 / \ 18 12 / \ / \ 2 6 3 4 / 7 */ // Create Binary Tree as shown Node root = newNode(10); root.left = newNode(40); root.right = newNode(36); root.right.left = newNode(18); root.right.right = newNode(12); root.right.left.left = newNode(2); root.right.left.right = newNode(6); root.right.right.left = newNode(3); root.right.right.right = newNode(4); root.right.right.right.left = newNode(7); // Print all nodes having // children as their factors Console.Write(getCount(root) +"\n"); }}// This code is contributed by sapnasingh4991 |
Javascript
<script>// Javascript program for Counting nodes// whose immediate children are its factors// A Tree nodeclass Node{ // Utility function to create a new node constructor(key) { this.key = key; this.left = this.right = null; }}// Function to check and print if// immediate children of a node// are its factors or notfunction areChilrenFactors(parent, a, b){ if (parent.key % a.key == 0 && parent.key % b.key == 0) return true; else return false;}// Function to get the// count of full Nodes in// a binary treefunction getCount(node){ // If tree is empty if (node == null) return 0; let q = []; // Do level order traversal // starting from root let count = 0; // Store the number of nodes // with both children as factors q.push(node); while (q.length != 0) { let temp = q.shift(); if (temp.left != null && temp.right != null) { if (areChilrenFactors( temp, temp.left, temp.right)) count++; } if (temp.left != null) q.push(temp.left); if (temp.right != null) q.push(temp.right); } return count;}// Function to find total no of nodes// In a given binary treefunction findSize(node){ // Base condition if (node == null) return 0; return 1 + findSize(node.left) + findSize(node.right);}// Driver Code/* 10 / \ 40 36 / \ 18 12 / \ / \ 2 6 3 4 / 7 */ // Create Binary Tree as shownlet root = new Node(10);root.left = new Node(40);root.right = new Node(36);root.right.left = new Node(18);root.right.right = new Node(12);root.right.left.left = new Node(2);root.right.left.right = new Node(6);root.right.right.left = new Node(3);root.right.right.right = new Node(4);root.right.right.right.left = new Node(7);// Print all nodes having// children as their factorsdocument.write(getCount(root) + "<br>");// This code is contributed by unknown2108</script> |
Output:
3
Time Complexity: O(N) where N is the number of nodes in the binary tree.
Auxiliary Space: O(N), as Level order uses N space for the call stack, where N is the number of nodes in the binary tree.
Efficient Method 2 (Using only one traversal without extra space):
we simply traverse the binary tree in preorder fashion and if a node has left and right child then we check that these childs are the factors of root node or not. If yes we increment the count variable.
Below is the implementation of above approach:
C++
// C++ program for Counting nodes whose// immediate children are its factors#include <bits/stdc++.h>using namespace std;// A Tree nodestruct Node { int data; struct Node* left; struct Node* right;};// Utility function to create a new nodeNode* newNode(int key){ Node* temp = new Node; temp->data = key; temp->left = temp->right = NULL; return temp;}// Function to check and print if immediate// children of a node are its factors or notbool areChilrenFactors(Node* parent, Node* a, Node* b){ if (parent->data % a->data == 0 && parent->data % b->data == 0) return true; else return false;}// Function to get the count of full Nodes// in a binary treevoid getCount(Node* root, int& count){ if (root == NULL) return; if (root->left != NULL && root->right != NULL) { if (areChilrenFactors(root, root->left, root->right)) { count++; } } getCount(root->left, count); getCount(root->right, count);}// Driver Codeint main(){ /* 10 / \ 40 36 / \ 18 12 / \ / \ 2 6 3 4 / 7 */ // Create Binary Tree as shown Node* root = newNode(10); root->left = newNode(40); root->right = newNode(36); root->right->left = newNode(18); root->right->right = newNode(12); root->right->left->left = newNode(2); root->right->left->right = newNode(6); root->right->right->left = newNode(3); root->right->right->right = newNode(4); root->right->right->right->left = newNode(7); // Print all nodes having // children as their factors int count = 0; getCount(root, count); cout << count << endl; return 0;}// This code is contributed by Yash Agarwal(yashagarwal2852002) |
Java
// Java program for Counting nodes whose// immediate children are its factorsimport java.io.*;// A Tree nodeclass Node { int data; Node left, right; Node(int key) { data = key; left = right = null; }}// Main classclass Main { // Function to check and print if immediate // children of a node are its factors or not static boolean areChildrenFactors(Node parent, Node a, Node b) { if (parent.data % a.data == 0 && parent.data % b.data == 0) return true; else return false; } // Function to get the count of full Nodes // in a binary tree static void getCount(Node root, int[] count) { if (root == null) return; if (root.left != null && root.right != null) { if (areChildrenFactors(root, root.left, root.right)) { count[0]++; } } getCount(root.left, count); getCount(root.right, count); } // Driver Code public static void main(String[] args) { /* 10 / \ 40 36 / \ 18 12 / \ / \ 2 6 3 4 / 7 */ // Create Binary Tree as shown Node root = new Node(10); root.left = new Node(40); root.right = new Node(36); root.right.left = new Node(18); root.right.right = new Node(12); root.right.left.left = new Node(2); root.right.left.right = new Node(6); root.right.right.left = new Node(3); root.right.right.right = new Node(4); root.right.right.right.left = new Node(7); // Print all nodes having // children as their factors int[] count = {0}; getCount(root, count); System.out.println(count[0]); }} |
Python3
# Python program for counting nodes whose# immediate children are its factors# A Tree nodeclass Node: def __init__(self, key): self.data = key self.left = None self.right = None# Function to check and print if immediate# children of a node are its factors or notdef areChildrenFactors(parent, a, b): if parent.data % a.data == 0 and parent.data % b.data == 0: return True else: return False# Function to get the count of full Nodes# in a binary treedef getCount(root, count): if root is None: return if root.left is not None and root.right is not None: if areChildrenFactors(root, root.left, root.right): count[0] += 1 getCount(root.left, count) getCount(root.right, count)# Driver Codeif __name__ == '__main__': # Create Binary Tree as shown root = Node(10) root.left = Node(40) root.right = Node(36) root.right.left = Node(18) root.right.right = Node(12) root.right.left.left = Node(2) root.right.left.right = Node(6) root.right.right.left = Node(3) root.right.right.right = Node(4) root.right.right.right.left = Node(7) # Print all nodes having children # as their factors count = [0] getCount(root, count) print(count[0]) |
C#
using System;// A Tree nodeclass Node{ public int data; public Node left, right; public Node(int key) { data = key; left = right = null; }}// Main classclass MainClass{ // Function to check and print if immediate // children of a node are its factors or not static bool AreChildrenFactors(Node parent, Node a, Node b) { if (parent.data % a.data == 0 && parent.data % b.data == 0) return true; else return false; } // Function to get the count of full Nodes // in a binary tree static void GetCount(Node root, int[] count) { if (root == null) return; if (root.left != null && root.right != null) { if (AreChildrenFactors(root, root.left, root.right)) { count[0]++; } } GetCount(root.left, count); GetCount(root.right, count); } // Driver Code public static void Main() { /* 10 / \ 40 36 / \ 18 12 / \ / \ 2 6 3 4 / 7 */ // Create Binary Tree as shown Node root = new Node(10); root.left = new Node(40); root.right = new Node(36); root.right.left = new Node(18); root.right.right = new Node(12); root.right.left.left = new Node(2); root.right.left.right = new Node(6); root.right.right.left = new Node(3); root.right.right.right = new Node(4); root.right.right.right.left = new Node(7); // Print all nodes having // children as their factors int[] count = {0}; GetCount(root, count); Console.WriteLine(count[0]); }} |
Javascript
// THIS CODE IS CONTRIBUTED BY KIRTI AGARWAL(KIRTIAGARWAL23121999)// JavaScript program for counting nodes whose// immediate children are its factorsclass Node{ constructor(data){ this.data = data; this.left = null; this.right = null; }}// utility function to create a new nodefunction newNode(key){ return new Node(key);}// Function to check and print if immediate// children of a node are its factors or notfunction areChilrenFactors(parent, a, b){ if (parent.data % a.data == 0 && parent.data % b.data == 0) return true; else return false;}let count = 0;// Function to get the count of full Nodes// in a binary treefunction getCount(root){ if (root == null) return; if (root.left != null && root.right != null) { if (areChilrenFactors(root, root.left, root.right)) { count++; } } getCount(root.left); getCount(root.right);}// Create Binary Tree as shownlet root = newNode(10); root.left = newNode(40);root.right = newNode(36); root.right.left = newNode(18);root.right.right = newNode(12); root.right.left.left = newNode(2);root.right.left.right = newNode(6);root.right.right.left = newNode(3);root.right.right.right = newNode(4);root.right.right.right.left = newNode(7);// Print all nodes having// children as their factorsgetCount(root);console.log(count); |
Output
3
Time Complexity: O(N) where N is the number of nodes in given binary tree.
Auxiliary Space: O(N) due to recursion call stack.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
