Given a binary tree and an integer K, the task is to print all the nodes having children with the same remainder when divided by K. Print “-1” if no such node exists.
Examples:
Input: K = 2
2
/ \
3 5
/ / \
7 8 6
Output: 2, 5
Explanation: Children of 2 = 3 and 5. Both give remainder 1 with 2, Similarly for 5, both children give remainder as 0Input: K = 5
9
/ \
7 8
/ \
4 3
Output: -1
Explanation: There is no node having both children with same remainder with K.
Approach: The task can be solved using a depth-first search. Traverse the Binary tree, and for each node, check:
- If the node has a left child
- If the node has a right child
- If both children give the same remainder with K
- Store all such nodes in a vector, and print its content at the end.
Below is the implementation of the above approach:
C++
// C++ implementation to print// the nodes having a single child#include <bits/stdc++.h>using namespace std;// Class of the Binary Tree nodestruct Node { int data; Node *left, *right; Node(int x) { data = x; left = right = NULL; }};vector<int> listOfNodes;// Function to find the nodes// having both child// and both of them % K are samevoid countNodes(Node* root, int& K){ // Base case if (root == NULL) return; // Condition to check if the // node is having both child // and both of them % K are same if (root->left != NULL && root->right != NULL && root->left->data % K == root->right->data % K) { listOfNodes.push_back(root->data); } // Traversing the left child countNodes(root->left, K); // Traversing the right child countNodes(root->right, K);}// Driver codeint main(){ // Constructing the binary tree Node* root = new Node(2); root->left = new Node(3); root->right = new Node(5); root->left->left = new Node(7); root->right->left = new Node(8); root->right->right = new Node(6); int K = 2; // Function calling countNodes(root, K); // Condition to check if there is // no such node having single child if (listOfNodes.size() == 0) printf("-1"); else { for (int value : listOfNodes) { cout << (value) << endl; } }} |
Java
// Java implementation to print// the nodes having a single childimport java.util.*;class GFG{// Class of the Binary Tree nodestatic class Node { int data; Node left, right; Node(int x) { data = x; left = right = null; }};static Vector<Integer> listOfNodes = new Vector<Integer>();// Function to find the nodes// having both child// and both of them % K are samestatic void countNodes(Node root, int K){ // Base case if (root == null) return; // Condition to check if the // node is having both child // and both of them % K are same if (root.left != null && root.right != null && root.left.data % K == root.right.data % K) { listOfNodes.add(root.data); } // Traversing the left child countNodes(root.left, K); // Traversing the right child countNodes(root.right, K);}// Driver codepublic static void main(String[] args){ // Constructing the binary tree Node root = new Node(2); root.left = new Node(3); root.right = new Node(5); root.left.left = new Node(7); root.right.left = new Node(8); root.right.right = new Node(6); int K = 2; // Function calling countNodes(root, K); // Condition to check if there is // no such node having single child if (listOfNodes.size() == 0) System.out.printf("-1"); else { for (int value : listOfNodes) { System.out.print((value) +"\n"); } }}}// This code is contributed by 29AjayKumar |
Python3
# Python code for the above approach# Class of the Binary Tree nodeclass Node: def __init__(self, x): self.data = x self.left = self.right = NonelistOfNodes = []# Function to find the nodes# having both child# and both of them % K are samedef countNodes(root, K): # Base case if (root == None): return 0 # Condition to check if the # node is having both child # and both of them % K are same if (root.left != None and root.right != None and root.left.data % K == root.right.data % K): listOfNodes.append(root.data) # Traversing the left child countNodes(root.left, K) # Traversing the right child countNodes(root.right, K)# Driver code# Constructing the binary treeroot = Node(2)root.left = Node(3)root.right = Node(5)root.left.left = Node(7)root.right.left = Node(8)root.right.right = Node(6)K = 2# Function callingcountNodes(root, K)# Condition to check if there is# no such node having single childif (len(listOfNodes) == 0): print("-1")else: for value in listOfNodes: print(value)# This code is contributed by Saurabh Jaiswal |
C#
// C# implementation to print// the nodes having a single childusing System;using System.Collections.Generic;public class GFG{ // Class of the Binary Tree node class Node { public int data; public Node left, right; public Node(int x) { data = x; left = right = null; } }; static List<int> listOfNodes = new List<int>(); // Function to find the nodes // having both child // and both of them % K are same static void countNodes(Node root, int K) { // Base case if (root == null) return; // Condition to check if the // node is having both child // and both of them % K are same if (root.left != null && root.right != null && root.left.data % K == root.right.data % K) { listOfNodes.Add(root.data); } // Traversing the left child countNodes(root.left, K); // Traversing the right child countNodes(root.right, K); } // Driver code public static void Main(String[] args) { // Constructing the binary tree Node root = new Node(2); root.left = new Node(3); root.right = new Node(5); root.left.left = new Node(7); root.right.left = new Node(8); root.right.right = new Node(6); int K = 2; // Function calling countNodes(root, K); // Condition to check if there is // no such node having single child if (listOfNodes.Count == 0) Console.Write("-1"); else { foreach (int values in listOfNodes) { Console.Write((values) +"\n"); } } }}// This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript code for the above approach // Class of the Binary Tree node class Node { constructor(x) { this.data = x; this.left = this.right = null; } }; let listOfNodes = []; // Function to find the nodes // having both child // and both of them % K are same function countNodes(root, K) { // Base case if (root == null) return 0; // Condition to check if the // node is having both child // and both of them % K are same if (root.left != null && root.right != null && root.left.data % K == root.right.data % K) { listOfNodes.push(root.data); } // Traversing the left child countNodes(root.left, K); // Traversing the right child countNodes(root.right, K); } // Driver code // Constructing the binary tree let root = new Node(2); root.left = new Node(3); root.right = new Node(5); root.left.left = new Node(7); root.right.left = new Node(8); root.right.right = new Node(6); let K = 2; // Function calling countNodes(root, K); // Condition to check if there is // no such node having single child if (listOfNodes.length == 0) document.write("-1"); else { for (let value of listOfNodes) { document.write((value) + "<br>"); } } // This code is contributed by Potta Lokesh </script> |
Output
2 5
Time Complexity: O(N)
Auxiliary Space: O(N)
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 neveropen!
Share your thoughts in the comments
