Tutorialspoint.dev

Number of subtrees having odd count of even numbers

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.



This article is attributed to GeeksforGeeks.org

tags:

Tree Tree

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter