Given a binary tree, find the number of subtrees having odd count of even numbers.
Examples:
Input : 2
/
1 3
/ /
4 10 8 5
/
6
Output : 6
The subtrees are 4, 6, 1, 8, 3
/ /
4 10 8 5
/
6
2
/
1 3
/ /
4 10 8 5
/
6
The idea is to recursively traverse the tree. For every node, recursively count even numbers in left and right subtrees. If root is also even, then add it also to count. If count becomes odd, increment result.
count = 0 // Initialize result
int countSubtrees(root)
{
if (root == NULL)
return 0;
// count even numbers in left subtree
int c = countSubtrees(root-> left);
// Add count of even numbers in right subtree
c += countSubtrees(root-> right);
// check if root data is an even number
if (root-> data % 2 == 0)
c += 1;
// If total count of even numbers
// for the subtree is odd
if (c % 2 != 0)
count++;
// return total count of even
// numbers of the subtree
return c;
}
C++
// C implementation to find number of // subtrees having odd count of even numbers #include <stdio.h> #include <stdlib.h> /* A binary tree Node */struct Node { int data; struct Node* left, *right; }; /* Helper function that allocates a new Node with the given data and NULL left and right pointers. */struct Node* newNode(int data) { struct Node* node = new Node; node->data = data; node->left = node->right = NULL; return(node); } // Returns count of subtrees having odd count of // even numbers int countRec(struct Node* root, int *pcount) { // base condition if (root == NULL) return 0; // count even nodes in left subtree int c = countRec(root->left, pcount); // Add even nodes in right subtree c += countRec(root->right, pcount); // Check if root data is an even number if (root->data % 2 == 0) c += 1; // if total count of even numbers // for the subtree is odd if (c % 2 != 0) (*pcount)++; // Total count of even nodes of the subtree return c; } // A wrapper over countRec() int countSubtrees(Node *root) { int count = 0; int *pcount = &count; countRec(root, pcount); return count; } // Driver program to test above int main() { // binary tree formation struct Node *root = newNode(2); /* 2 */ root->left = newNode(1); /* / */ root->right = newNode(3); /* 1 3 */ root->left->left = newNode(4); /* / / */ root->left->right = newNode(10); /* 4 10 8 5 */ root->right->left = newNode(8); /* / */ root->right->right = newNode(5); /* 6 */ root->left->right->left = newNode(6); printf("Count = %d", countSubtrees(root)); return 0; } |
Java
// Java implementation to find number of // subtrees having odd count of even numbers import java.util.*; class GfG { /* A binary tree Node */static class Node { int data; Node left, right; } /* Helper function that allocates a new Node with the given data and NULL left and right pointers. */static Node newNode(int data) { Node node = new Node(); node.data = data; node.left = null; node.right = null; return(node); } // Returns count of subtrees having odd count of // even numbers static class P { int pcount = 0; } static int countRec(Node root, P p) { // base condition if (root == null) return 0; // count even nodes in left subtree int c = countRec(root.left, p); // Add even nodes in right subtree c += countRec(root.right, p); // Check if root data is an even number if (root.data % 2 == 0) c += 1; // if total count of even numbers // for the subtree is odd if (c % 2 != 0) (p.pcount)++; // Total count of even nodes of the subtree return c; } // A wrapper over countRec() static int countSubtrees(Node root) { P p = new P(); countRec(root, p); return p.pcount; } // Driver program to test above public static void main(String[] args) { // binary tree formation Node root = newNode(2); /* 2 */ root.left = newNode(1); /* / */ root.right = newNode(3); /* 1 3 */ root.left.left = newNode(4); /* / / */ root.left.right = newNode(10); /* 4 10 8 5 */ root.right.left = newNode(8); /* / */ root.right.right = newNode(5); /* 6 */ root.left.right.left = newNode(6); System.out.println("Count = " + countSubtrees(root)); } } |
Python3
# Python3 implementation to find number of # subtrees having odd count of even numbers # Helper class that allocates a new Node # with the given data and None left and # right pointers. class newNode: def __init__(self, data): self.data = data self.left = self.right = None # Returns count of subtrees having odd # count of even numbers def countRec(root, pcount): # base condition if (root == None): return 0 # count even nodes in left subtree c = countRec(root.left, pcount) # Add even nodes in right subtree c += countRec(root.right, pcount) # Check if root data is an even number if (root.data % 2 == 0): c += 1 # if total count of even numbers # for the subtree is odd if c % 2 != 0: pcount[0] += 1 # Total count of even nodes of # the subtree return c # A wrapper over countRec() def countSubtrees(root): count = [0] pcount = count countRec(root, pcount) return count[0] # Driver Code if __name__ == '__main__': # binary tree formation root = newNode(2) # 2 root.left = newNode(1) # / root.right = newNode(3) # 1 3 root.left.left = newNode(4) # / / root.left.right = newNode(10) # 4 10 8 5 root.right.left = newNode(8) # / root.right.right = newNode(5) # 6 root.left.right.left = newNode(6) print("Count = ", countSubtrees(root)) # This code is contributed by PranchalK |
Output:
Count = 6
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
leave a comment
0 Comments