# Remove all subtree of Even values node in binary tree

The problem revolves around removing all subtrees from a binary tree that are rooted at nodes containing even values. The objective is to create a modified binary tree where these subtrees are pruned.

## Problem Statement

Given a binary tree, the task is to remove all subtrees rooted at nodes containing even values. The program should then print the preorder traversal of the modified binary tree.

## Example

Consider two binary trees, labeled A and B:

Binary Tree A (Before):

``````         1
/   \
2     7
/ \     \
6   3     8
/  \
10   12``````

Binary Tree B (Before):

``````         10
/   \
2     7
/ \     \
6   4     8
/ \
8   20``````

After removing subtrees rooted at even value nodes, the modified binary trees become:

Binary Tree A (After):

``````         1
/   \
2     7
\
3``````

Binary Tree B (After):

``````         10
\
7``````

## Idea to Solve

The problem can be solved using a recursive approach. The `deleteEvenSubTree` function takes a node as input and recursively deletes subtrees rooted at nodes containing even values. If a node contains an even value and is a leaf node (has no children), it is freed, and a null pointer is returned to indicate that this subtree should be removed from the main tree.

## Pseudocode

``````function deleteEvenSubTree(node):
if node is not null:
recursively call deleteEvenSubTree for left child
recursively call deleteEvenSubTree for right child
if node is a leaf node and has an even value:
free the node
return null
else:
return node

main:
create binary tree
construct tree
print "Before Delete Tree"
perform preorder traversal on the original tree
call deleteEvenSubTree with root node
print "After Delete Tree"
perform preorder traversal on the modified tree``````

## Algorithm Explanation

1. The `deleteEvenSubTree` function recursively traverses the binary tree and deletes subtrees rooted at nodes containing even values.
2. During traversal, if a node is a leaf node and has an even value, it is freed (memory deallocated), and a null pointer is returned to indicate that this subtree should be removed from the main tree.
3. The modified tree is returned after the removal of subtrees.

## Program Solution

``````// C Program
// Remove all subtree of Even values node in binary tree
#include <stdio.h>
#include <stdlib.h>

// Tree Node
struct TreeNode
{
int data;
struct TreeNode *left;
struct TreeNode *right;
};
// Binary Tree
struct BinaryTree
{
struct TreeNode *root;
};
// Create new tree
struct BinaryTree *newTree()
{
// Create dynamic node
struct BinaryTree *tree =
(struct BinaryTree *) malloc(sizeof(struct BinaryTree));
if (tree != NULL)
{
tree->root = NULL;
}
else
{
printf("Memory Overflow to Create tree Tree\n");
}
//return new tree
return tree;
}
// This is creates and returns the new binary tree node
struct TreeNode *newNode(int data)
{
// Create dynamic node
struct TreeNode *new_node =
(struct TreeNode *) malloc(sizeof(struct TreeNode));
if (new_node != NULL)
{
//Set data and pointer values
new_node->data = data;
new_node->left = NULL;
new_node->right = NULL;
}
else
{
//This is indicates,
// segmentation fault or memory overflow problem
printf("Memory Overflow\n");
exit(0);
}
//return new node
return new_node;
}

struct TreeNode *deleteEvenSubTree(struct TreeNode *node)
{
if (node != NULL)
{
node->left = deleteEvenSubTree(node->left);
node->right = deleteEvenSubTree(node->right);
if (node->left == NULL &&
node->right == NULL &&
node->data % 2 == 0)
{
// free Node
free(node);
return NULL;
}
}
return node;
}
int main(int argc, char
const *argv[])
{
struct BinaryTree *tree1 = newTree();
struct BinaryTree *tree2 = newTree();
/*
1
/   \
2     7
/ \     \
6   3     8
/  \
10   12
------------
Binary tree A
*/
// Tree A
tree1->root = newNode(1);
tree1->root->left = newNode(2);
tree1->root->right = newNode(7);
tree1->root->right->right = newNode(8);
tree1->root->left->right = newNode(3);
tree1->root->left->left = newNode(6);
tree1->root->right->right->left = newNode(10);
tree1->root->right->right->right = newNode(12);
/*
Construct Tree number 2
---------

10
/   \
2     7
/ \     \
6   4     8
/ \
8   20
------------
Binary tree B
*/
// Tree B
tree2->root = newNode(10);
tree2->root->left = newNode(2);
tree2->root->right = newNode(7);
tree2->root->right->right = newNode(8);
tree2->root->left->right = newNode(4);
tree2->root->left->left = newNode(6);
tree2->root->left->right->left = newNode(8);
tree2->root->left->right->right = newNode(20);
// Test A
printf("\n Before Delete Tree 1 \n");
preorder(tree1->root);
// Remove subtree which contains all Even nodes
tree1->root = deleteEvenSubTree(tree1->root);
/*
1
/   \
2     7
\
3
------------
After delete Even node subtrees
*/
printf("\n After Delete Tree 1 \n");
preorder(tree1->root);
// Test B
printf("\n Before Delete Tree 2 \n");
preorder(tree2->root);
// Remove subtree which contains all Even nodes
tree2->root = deleteEvenSubTree(tree2->root);
/*
10
\
7
------------
After delete Even node subtrees
*/
printf("\n After Delete Tree 2 \n");
preorder(tree2->root);
return 0;
}``````

#### Output

`````` Before Delete Tree 1
1  2  6  3  7  8  10  12
After Delete Tree 1
1  2  3  7
Before Delete Tree 2
10  2  6  4  8  20  7  8
After Delete Tree 2
10  7``````
``````/*
Java program for
Remove all subtree of Even values node in binary tree
*/
// Binary Tree node
class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
// Set initial value
this.root = null;
}
// Display preorder view of binary tree
public void preorder(TreeNode node)
{
if (node != null)
{
//Print node value
System.out.print("  " + node.data);
preorder(node.left);
preorder(node.right);
}
}
public TreeNode deleteEvenSubTree(TreeNode node)
{
if (node != null)
{
node.left = deleteEvenSubTree(node.left);
node.right = deleteEvenSubTree(node.right);
if (node.left == null &&
node.right == null &&
node.data % 2 == 0)
{
// delete Node
return null;
}
}
return node;
}
public static void main(String[] args)
{
BinaryTree tree1 = new BinaryTree();
BinaryTree tree2 = new BinaryTree();
/*
1
/   \
2     7
/ \     \
6   3     8
/  \
10   12
------------
Binary tree A
*/
// Tree A
tree1.root = new TreeNode(1);
tree1.root.left = new TreeNode(2);
tree1.root.right = new TreeNode(7);
tree1.root.right.right = new TreeNode(8);
tree1.root.left.right = new TreeNode(3);
tree1.root.left.left = new TreeNode(6);
tree1.root.right.right.left = new TreeNode(10);
tree1.root.right.right.right = new TreeNode(12);
/*
Construct Tree number 2
---------
10
/   \
2     7
/ \     \
6   4     8
/ \
8   20
------------
Binary tree B
*/
// Tree B
tree2.root = new TreeNode(10);
tree2.root.left = new TreeNode(2);
tree2.root.right = new TreeNode(7);
tree2.root.right.right = new TreeNode(8);
tree2.root.left.right = new TreeNode(4);
tree2.root.left.left = new TreeNode(6);
tree2.root.left.right.left = new TreeNode(8);
tree2.root.left.right.right = new TreeNode(20);
// Test A
System.out.print("\n Before Delete Tree 1 \n");
tree1.preorder(tree1.root);
// Remove subtree which contains all Even nodes
tree1.root = tree1.deleteEvenSubTree(tree1.root);
/*
1
/   \
2     7
\
3
------------
After delete Even node subtrees
*/
System.out.print("\n After Delete Tree 1 \n");
tree1.preorder(tree1.root);
// Test B
System.out.print("\n Before Delete Tree 2 \n");
tree2.preorder(tree2.root);
// Remove subtree which contains all Even nodes
tree2.root = tree2.deleteEvenSubTree(tree2.root);
/*
10
\
7
------------
After delete Even node subtrees
*/
System.out.print("\n After Delete Tree 2 \n");
tree2.preorder(tree2.root);
}
}``````

#### Output

`````` Before Delete Tree 1
1  2  6  3  7  8  10  12
After Delete Tree 1
1  2  3  7
Before Delete Tree 2
10  2  6  4  8  20  7  8
After Delete Tree 2
10  7``````
``````// Include header file
#include <iostream>

using namespace std;
/*
C++ program for
Remove all subtree of Even values node in binary tree
*/
// Binary Tree node
class TreeNode
{
public: int data;
TreeNode *left;
TreeNode *right;
TreeNode(int data)
{
// Set node value
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
class BinaryTree
{
public: TreeNode *root;
BinaryTree()
{
this->root = NULL;
}
// Display preorder view of binary tree
void preorder(TreeNode *node)
{
if (node != NULL)
{
//Print node value
cout << "  " << node->data;
this->preorder(node->left);
this->preorder(node->right);
}
}
TreeNode *deleteEvenSubTree(TreeNode *node)
{
if (node != NULL)
{
node->left = this->deleteEvenSubTree(node->left);
node->right = this->deleteEvenSubTree(node->right);
if (node->left == NULL &&
node->right == NULL &&
node->data % 2 == 0)
{
// delete Node
delete node;
return NULL;
}
}
return node;
}
};
int main()
{
BinaryTree *tree1 = new BinaryTree();
BinaryTree *tree2 = new BinaryTree();
/*
1
/   \
2     7
/ \     \
6   3     8
/  \
10   12
------------
Binary tree A
*/
// Tree A
tree1->root = new TreeNode(1);
tree1->root->left = new TreeNode(2);
tree1->root->right = new TreeNode(7);
tree1->root->right->right = new TreeNode(8);
tree1->root->left->right = new TreeNode(3);
tree1->root->left->left = new TreeNode(6);
tree1->root->right->right->left = new TreeNode(10);
tree1->root->right->right->right = new TreeNode(12);
/*
Construct Tree number 2
---------
10
/   \
2     7
/ \     \
6   4     8
/ \
8   20
------------
Binary tree B
*/
// Tree B
tree2->root = new TreeNode(10);
tree2->root->left = new TreeNode(2);
tree2->root->right = new TreeNode(7);
tree2->root->right->right = new TreeNode(8);
tree2->root->left->right = new TreeNode(4);
tree2->root->left->left = new TreeNode(6);
tree2->root->left->right->left = new TreeNode(8);
tree2->root->left->right->right = new TreeNode(20);
// Test A
cout << "\n Before Delete Tree 1 \n";
tree1->preorder(tree1->root);
// Remove subtree which contains all Even nodes
tree1->root = tree1->deleteEvenSubTree(tree1->root);
/*
1
/   \
2     7
\
3
------------
After delete Even node subtrees
*/
cout << "\n After Delete Tree 1 \n";
tree1->preorder(tree1->root);
// Test B
cout << "\n Before Delete Tree 2 \n";
tree2->preorder(tree2->root);
// Remove subtree which contains all Even nodes
tree2->root = tree2->deleteEvenSubTree(tree2->root);
/*
10
\
7
------------
After delete Even node subtrees
*/
cout << "\n After Delete Tree 2 \n";
tree2->preorder(tree2->root);
return 0;
}``````

#### Output

`````` Before Delete Tree 1
1  2  6  3  7  8  10  12
After Delete Tree 1
1  2  3  7
Before Delete Tree 2
10  2  6  4  8  20  7  8
After Delete Tree 2
10  7``````
``````// Include namespace system
using System;
/*
Csharp program for
Remove all subtree of Even values node in binary tree
*/
// Binary Tree node
public class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
// Set initial value
this.root = null;
}
// Display preorder view of binary tree
public void preorder(TreeNode node)
{
if (node != null)
{
//Print node value
Console.Write("  " + node.data);
this.preorder(node.left);
this.preorder(node.right);
}
}
public TreeNode deleteEvenSubTree(TreeNode node)
{
if (node != null)
{
node.left = this.deleteEvenSubTree(node.left);
node.right = this.deleteEvenSubTree(node.right);
if (node.left == null &&
node.right == null &&
node.data % 2 == 0)
{
// delete Node
return null;
}
}
return node;
}
public static void Main(String[] args)
{
BinaryTree tree1 = new BinaryTree();
BinaryTree tree2 = new BinaryTree();
/*
1
/   \
2     7
/ \     \
6   3     8
/  \
10   12
------------
Binary tree A
*/
// Tree A
tree1.root = new TreeNode(1);
tree1.root.left = new TreeNode(2);
tree1.root.right = new TreeNode(7);
tree1.root.right.right = new TreeNode(8);
tree1.root.left.right = new TreeNode(3);
tree1.root.left.left = new TreeNode(6);
tree1.root.right.right.left = new TreeNode(10);
tree1.root.right.right.right = new TreeNode(12);
/*
Construct Tree number 2
---------
10
/   \
2     7
/ \     \
6   4     8
/ \
8   20
------------
Binary tree B
*/
// Tree B
tree2.root = new TreeNode(10);
tree2.root.left = new TreeNode(2);
tree2.root.right = new TreeNode(7);
tree2.root.right.right = new TreeNode(8);
tree2.root.left.right = new TreeNode(4);
tree2.root.left.left = new TreeNode(6);
tree2.root.left.right.left = new TreeNode(8);
tree2.root.left.right.right = new TreeNode(20);
// Test A
Console.Write("\n Before Delete Tree 1 \n");
tree1.preorder(tree1.root);
// Remove subtree which contains all Even nodes
tree1.root = tree1.deleteEvenSubTree(tree1.root);
/*
1
/   \
2     7
\
3
------------
After delete Even node subtrees
*/
Console.Write("\n After Delete Tree 1 \n");
tree1.preorder(tree1.root);
// Test B
Console.Write("\n Before Delete Tree 2 \n");
tree2.preorder(tree2.root);
// Remove subtree which contains all Even nodes
tree2.root = tree2.deleteEvenSubTree(tree2.root);
/*
10
\
7
------------
After delete Even node subtrees
*/
Console.Write("\n After Delete Tree 2 \n");
tree2.preorder(tree2.root);
}
}``````

#### Output

`````` Before Delete Tree 1
1  2  6  3  7  8  10  12
After Delete Tree 1
1  2  3  7
Before Delete Tree 2
10  2  6  4  8  20  7  8
After Delete Tree 2
10  7``````
``````package main
import "fmt"
/*
Go program for
Remove all subtree of Even values node in binary tree
*/
// Binary Tree node
type TreeNode struct {
data int
left * TreeNode
right * TreeNode
}
func getTreeNode(data int) * TreeNode {
var me *TreeNode = &TreeNode {}
// Set node value
me.data = data
me.left = nil
me.right = nil
return me
}
type BinaryTree struct {
root * TreeNode
}
func getBinaryTree() * BinaryTree {
var me *BinaryTree = &BinaryTree {}
// Set initial value
me.root = nil
return me
}
// Display preorder view of binary tree
func(this BinaryTree) preorder(node * TreeNode) {
if node != nil {
//Print node value
fmt.Print("  ", node.data)
this.preorder(node.left)
this.preorder(node.right)
}
}
func(this BinaryTree) deleteEvenSubTree(node * TreeNode) * TreeNode {
if node != nil {
node.left = this.deleteEvenSubTree(node.left)
node.right = this.deleteEvenSubTree(node.right)
if node.left == nil &&
node.right == nil &&
node.data % 2 == 0 {
// delete Node
return nil
}
}
return node
}
func main() {
var tree1 * BinaryTree = getBinaryTree()
var tree2 * BinaryTree = getBinaryTree()
/*
1
/   \
2     7
/ \     \
6   3     8
/  \
10   12
------------
Binary tree A
*/
// Tree A
tree1.root = getTreeNode(1)
tree1.root.left = getTreeNode(2)
tree1.root.right = getTreeNode(7)
tree1.root.right.right = getTreeNode(8)
tree1.root.left.right = getTreeNode(3)
tree1.root.left.left = getTreeNode(6)
tree1.root.right.right.left = getTreeNode(10)
tree1.root.right.right.right = getTreeNode(12)
/*
Construct Tree number 2
---------
10
/   \
2     7
/ \     \
6   4     8
/ \
8   20
------------
Binary tree B
*/
// Tree B
tree2.root = getTreeNode(10)
tree2.root.left = getTreeNode(2)
tree2.root.right = getTreeNode(7)
tree2.root.right.right = getTreeNode(8)
tree2.root.left.right = getTreeNode(4)
tree2.root.left.left = getTreeNode(6)
tree2.root.left.right.left = getTreeNode(8)
tree2.root.left.right.right = getTreeNode(20)
// Test A
fmt.Print("\n Before Delete Tree 1 \n")
tree1.preorder(tree1.root)
// Remove subtree which contains all Even nodes
tree1.root = tree1.deleteEvenSubTree(tree1.root)
/*
1
/   \
2     7
\
3
------------
After delete Even node subtrees
*/
fmt.Print("\n After Delete Tree 1 \n")
tree1.preorder(tree1.root)
// Test B
fmt.Print("\n Before Delete Tree 2 \n")
tree2.preorder(tree2.root)
// Remove subtree which contains all Even nodes
tree2.root = tree2.deleteEvenSubTree(tree2.root)
/*
10
\
7
------------
After delete Even node subtrees
*/
fmt.Print("\n After Delete Tree 2 \n")
tree2.preorder(tree2.root)
}``````

#### Output

`````` Before Delete Tree 1
1  2  6  3  7  8  10  12
After Delete Tree 1
1  2  3  7
Before Delete Tree 2
10  2  6  4  8  20  7  8
After Delete Tree 2
10  7``````
``````<?php
/*
Php program for
Remove all subtree of Even values node in binary tree
*/
// Binary Tree node
class TreeNode
{
public \$data;
public \$left;
public \$right;
public	function __construct(\$data)
{
// Set node value
\$this->data = \$data;
\$this->left = NULL;
\$this->right = NULL;
}
}
class BinaryTree
{
public \$root;
public	function __construct()
{
\$this->root = NULL;
}
// Display preorder view of binary tree
public	function preorder(\$node)
{
if (\$node != NULL)
{
//Print node value
echo("  ".\$node->data);
\$this->preorder(\$node->left);
\$this->preorder(\$node->right);
}
}
public	function deleteEvenSubTree(\$node)
{
if (\$node != NULL)
{
\$node->left = \$this->deleteEvenSubTree(\$node->left);
\$node->right = \$this->deleteEvenSubTree(\$node->right);
if (\$node->left == NULL &&
\$node->right == NULL &&
\$node->data % 2 == 0)
{
// delete Node
return NULL;
}
}
return \$node;
}
}

function main()
{
\$tree1 = new BinaryTree();
\$tree2 = new BinaryTree();
/*
1
/   \
2     7
/ \     \
6   3     8
/  \
10   12
------------
Binary tree A
*/
// Tree A
\$tree1->root = new TreeNode(1);
\$tree1->root->left = new TreeNode(2);
\$tree1->root->right = new TreeNode(7);
\$tree1->root->right->right = new TreeNode(8);
\$tree1->root->left->right = new TreeNode(3);
\$tree1->root->left->left = new TreeNode(6);
\$tree1->root->right->right->left = new TreeNode(10);
\$tree1->root->right->right->right = new TreeNode(12);
/*
Construct Tree number 2
---------
10
/   \
2     7
/ \     \
6   4     8
/ \
8   20
------------
Binary tree B
*/
// Tree B
\$tree2->root = new TreeNode(10);
\$tree2->root->left = new TreeNode(2);
\$tree2->root->right = new TreeNode(7);
\$tree2->root->right->right = new TreeNode(8);
\$tree2->root->left->right = new TreeNode(4);
\$tree2->root->left->left = new TreeNode(6);
\$tree2->root->left->right->left = new TreeNode(8);
\$tree2->root->left->right->right = new TreeNode(20);
// Test A
echo("\n Before Delete Tree 1 \n");
\$tree1->preorder(\$tree1->root);
// Remove subtree which contains all Even nodes
\$tree1->root = \$tree1->deleteEvenSubTree(\$tree1->root);
/*
1
/   \
2     7
\
3
------------
After delete Even node subtrees
*/
echo("\n After Delete Tree 1 \n");
\$tree1->preorder(\$tree1->root);
// Test B
echo("\n Before Delete Tree 2 \n");
\$tree2->preorder(\$tree2->root);
// Remove subtree which contains all Even nodes
\$tree2->root = \$tree2->deleteEvenSubTree(\$tree2->root);
/*
10
\
7
------------
After delete Even node subtrees
*/
echo("\n After Delete Tree 2 \n");
\$tree2->preorder(\$tree2->root);
}
main();``````

#### Output

`````` Before Delete Tree 1
1  2  6  3  7  8  10  12
After Delete Tree 1
1  2  3  7
Before Delete Tree 2
10  2  6  4  8  20  7  8
After Delete Tree 2
10  7``````
``````/*
Node JS program for
Remove all subtree of Even values node in binary tree
*/
// Binary Tree node
class TreeNode
{
constructor(data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
constructor()
{
this.root = null;
}
// Display preorder view of binary tree
preorder(node)
{
if (node != null)
{
//Print node value
process.stdout.write("  " + node.data);
this.preorder(node.left);
this.preorder(node.right);
}
}
deleteEvenSubTree(node)
{
if (node != null)
{
node.left = this.deleteEvenSubTree(node.left);
node.right = this.deleteEvenSubTree(node.right);
if (node.left == null &&
node.right == null &&
node.data % 2 == 0)
{
// delete Node
return null;
}
}
return node;
}
}

function main()
{
var tree1 = new BinaryTree();
var tree2 = new BinaryTree();
/*
1
/   \
2     7
/ \     \
6   3     8
/  \
10   12
------------
Binary tree A
*/
// Tree A
tree1.root = new TreeNode(1);
tree1.root.left = new TreeNode(2);
tree1.root.right = new TreeNode(7);
tree1.root.right.right = new TreeNode(8);
tree1.root.left.right = new TreeNode(3);
tree1.root.left.left = new TreeNode(6);
tree1.root.right.right.left = new TreeNode(10);
tree1.root.right.right.right = new TreeNode(12);
/*
Construct Tree number 2
---------
10
/   \
2     7
/ \     \
6   4     8
/ \
8   20
------------
Binary tree B
*/
// Tree B
tree2.root = new TreeNode(10);
tree2.root.left = new TreeNode(2);
tree2.root.right = new TreeNode(7);
tree2.root.right.right = new TreeNode(8);
tree2.root.left.right = new TreeNode(4);
tree2.root.left.left = new TreeNode(6);
tree2.root.left.right.left = new TreeNode(8);
tree2.root.left.right.right = new TreeNode(20);
// Test A
process.stdout.write("\n Before Delete Tree 1 \n");
tree1.preorder(tree1.root);
// Remove subtree which contains all Even nodes
tree1.root = tree1.deleteEvenSubTree(tree1.root);
/*
1
/   \
2     7
\
3
------------
After delete Even node subtrees
*/
process.stdout.write("\n After Delete Tree 1 \n");
tree1.preorder(tree1.root);
// Test B
process.stdout.write("\n Before Delete Tree 2 \n");
tree2.preorder(tree2.root);
// Remove subtree which contains all Even nodes
tree2.root = tree2.deleteEvenSubTree(tree2.root);
/*
10
\
7
------------
After delete Even node subtrees
*/
process.stdout.write("\n After Delete Tree 2 \n");
tree2.preorder(tree2.root);
}
main();``````

#### Output

`````` Before Delete Tree 1
1  2  6  3  7  8  10  12
After Delete Tree 1
1  2  3  7
Before Delete Tree 2
10  2  6  4  8  20  7  8
After Delete Tree 2
10  7``````
``````#  Python 3 program for
#  Remove all subtree of Even values node in binary tree

#  Binary Tree node
class TreeNode :
def __init__(self, data) :
#  Set node value
self.data = data
self.left = None
self.right = None

class BinaryTree :
def __init__(self) :
self.root = None

#  Display preorder view of binary tree
def preorder(self, node) :
if (node != None) :
# Print node value
print("  ", node.data, end = "")
self.preorder(node.left)
self.preorder(node.right)

def deleteEvenSubTree(self, node) :
if (node != None) :
node.left = self.deleteEvenSubTree(node.left)
node.right = self.deleteEvenSubTree(node.right)
if (node.left == None and
node.right == None and
node.data % 2 == 0) :
#  delete Node
return None

return node

def main() :
tree1 = BinaryTree()
tree2 = BinaryTree()
#         1
#       /   \
#      2     7
#     / \     \
#    6   3     8
#             /  \
#            10   12
#    ------------
#    Binary tree A
#  Tree A
tree1.root = TreeNode(1)
tree1.root.left = TreeNode(2)
tree1.root.right = TreeNode(7)
tree1.root.right.right = TreeNode(8)
tree1.root.left.right = TreeNode(3)
tree1.root.left.left = TreeNode(6)
tree1.root.right.right.left = TreeNode(10)
tree1.root.right.right.right = TreeNode(12)
#    Construct Tree number 2
#    ---------
#         10
#       /   \
#      2     7
#     / \     \
#    6   4     8
#       / \
#      8   20
#    ------------
#    Binary tree B
#  Tree B
tree2.root = TreeNode(10)
tree2.root.left = TreeNode(2)
tree2.root.right = TreeNode(7)
tree2.root.right.right = TreeNode(8)
tree2.root.left.right = TreeNode(4)
tree2.root.left.left = TreeNode(6)
tree2.root.left.right.left = TreeNode(8)
tree2.root.left.right.right = TreeNode(20)
#  Test A
print("\n Before Delete Tree 1 ")
tree1.preorder(tree1.root)
#  Remove subtree which contains all Even nodes
tree1.root = tree1.deleteEvenSubTree(tree1.root)
#     1
#   /   \
#  2     7
#   \
#    3
#    ------------
#    After delete Even node subtrees
print("\n After Delete Tree 1 ")
tree1.preorder(tree1.root)
#  Test B
print("\n Before Delete Tree 2 ")
tree2.preorder(tree2.root)
#  Remove subtree which contains all Even nodes
tree2.root = tree2.deleteEvenSubTree(tree2.root)
#   10
#     \
#      7
#    ------------
#    After delete Even node subtrees
print("\n After Delete Tree 2 ")
tree2.preorder(tree2.root)

if __name__ == "__main__": main()``````

#### Output

`````` Before Delete Tree 1
1   2   6   3   7   8   10   12
After Delete Tree 1
1   2   3   7
Before Delete Tree 2
10   2   6   4   8   20   7   8
After Delete Tree 2
10   7``````
``````#  Ruby program for
#  Remove all subtree of Even values node in binary tree

#  Binary Tree node
class TreeNode
# Define the accessor and reader of class TreeNode
attr_accessor :data, :left, :right
def initialize(data)
#  Set node value
self.data = data
self.left = nil
self.right = nil
end

end

class BinaryTree
# Define the accessor and reader of class BinaryTree
attr_accessor :root
def initialize()
self.root = nil
end

#  Display preorder view of binary tree
def preorder(node)
if (node != nil)
# Print node value
print("  ", node.data)
self.preorder(node.left)
self.preorder(node.right)
end

end

def deleteEvenSubTree(node)
if (node != nil)
node.left = self.deleteEvenSubTree(node.left)
node.right = self.deleteEvenSubTree(node.right)
if (node.left == nil &&
node.right == nil &&
node.data % 2 == 0)
#  delete Node
return nil
end

end

return node
end

end

def main()
tree1 = BinaryTree.new()
tree2 = BinaryTree.new()
#         1
#       /   \
#      2     7
#     / \     \
#    6   3     8
#             /  \
#            10   12
#    ------------
#    Binary tree A
#  Tree A
tree1.root = TreeNode.new(1)
tree1.root.left = TreeNode.new(2)
tree1.root.right = TreeNode.new(7)
tree1.root.right.right = TreeNode.new(8)
tree1.root.left.right = TreeNode.new(3)
tree1.root.left.left = TreeNode.new(6)
tree1.root.right.right.left = TreeNode.new(10)
tree1.root.right.right.right = TreeNode.new(12)
#    Construct Tree number 2
#    ---------
#         10
#       /   \
#      2     7
#     / \     \
#    6   4     8
#       / \
#      8   20
#    ------------
#    Binary tree B
#  Tree B
tree2.root = TreeNode.new(10)
tree2.root.left = TreeNode.new(2)
tree2.root.right = TreeNode.new(7)
tree2.root.right.right = TreeNode.new(8)
tree2.root.left.right = TreeNode.new(4)
tree2.root.left.left = TreeNode.new(6)
tree2.root.left.right.left = TreeNode.new(8)
tree2.root.left.right.right = TreeNode.new(20)
#  Test A
print("\n Before Delete Tree 1 \n")
tree1.preorder(tree1.root)
#  Remove subtree which contains all Even nodes
tree1.root = tree1.deleteEvenSubTree(tree1.root)
#     1
#   /   \
#  2     7
#   \
#    3
#    ------------
#    After delete Even node subtrees
print("\n After Delete Tree 1 \n")
tree1.preorder(tree1.root)
#  Test B
print("\n Before Delete Tree 2 \n")
tree2.preorder(tree2.root)
#  Remove subtree which contains all Even nodes
tree2.root = tree2.deleteEvenSubTree(tree2.root)
#   10
#     \
#      7
#    ------------
#    After delete Even node subtrees
print("\n After Delete Tree 2 \n")
tree2.preorder(tree2.root)
end

main()``````

#### Output

`````` Before Delete Tree 1
1  2  6  3  7  8  10  12
After Delete Tree 1
1  2  3  7
Before Delete Tree 2
10  2  6  4  8  20  7  8
After Delete Tree 2
10  7``````
``````/*
Scala program for
Remove all subtree of Even values node in binary tree
*/
// Binary Tree node
class TreeNode(var data: Int,
var left: TreeNode,
var right: TreeNode)
{
def this(data: Int)
{
// Set node value
this(data,null,null);
}
}
class BinaryTree(var root: TreeNode)
{
def this()
{
this(null);
}
// Display preorder view of binary tree
def preorder(node: TreeNode): Unit = {
if (node != null)
{
//Print node value
print("  " + node.data);
preorder(node.left);
preorder(node.right);
}
}
def deleteEvenSubTree(node: TreeNode): TreeNode = {
if (node != null)
{
node.left = deleteEvenSubTree(node.left);
node.right = deleteEvenSubTree(node.right);
if (node.left == null &&
node.right == null &&
node.data % 2 == 0)
{
// delete Node
return null;
}
}
return node;
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree1: BinaryTree = new BinaryTree();
var tree2: BinaryTree = new BinaryTree();
/*
1
/   \
2     7
/ \     \
6   3     8
/  \
10   12
------------
Binary tree A
*/
// Tree A
tree1.root = new TreeNode(1);
tree1.root.left = new TreeNode(2);
tree1.root.right = new TreeNode(7);
tree1.root.right.right = new TreeNode(8);
tree1.root.left.right = new TreeNode(3);
tree1.root.left.left = new TreeNode(6);
tree1.root.right.right.left = new TreeNode(10);
tree1.root.right.right.right = new TreeNode(12);
/*
Construct Tree number 2
---------
10
/   \
2     7
/ \     \
6   4     8
/ \
8   20
------------
Binary tree B
*/
// Tree B
tree2.root = new TreeNode(10);
tree2.root.left = new TreeNode(2);
tree2.root.right = new TreeNode(7);
tree2.root.right.right = new TreeNode(8);
tree2.root.left.right = new TreeNode(4);
tree2.root.left.left = new TreeNode(6);
tree2.root.left.right.left = new TreeNode(8);
tree2.root.left.right.right = new TreeNode(20);
// Test A
print("\n Before Delete Tree 1 \n");
tree1.preorder(tree1.root);
// Remove subtree which contains all Even nodes
tree1.root = tree1.deleteEvenSubTree(tree1.root);
/*
1
/   \
2     7
\
3
------------
After delete Even node subtrees
*/
print("\n After Delete Tree 1 \n");
tree1.preorder(tree1.root);
// Test B
print("\n Before Delete Tree 2 \n");
tree2.preorder(tree2.root);
// Remove subtree which contains all Even nodes
tree2.root = tree2.deleteEvenSubTree(tree2.root);
/*
10
\
7
------------
After delete Even node subtrees
*/
print("\n After Delete Tree 2 \n");
tree2.preorder(tree2.root);
}
}``````

#### Output

`````` Before Delete Tree 1
1  2  6  3  7  8  10  12
After Delete Tree 1
1  2  3  7
Before Delete Tree 2
10  2  6  4  8  20  7  8
After Delete Tree 2
10  7``````
``````/*
Swift 4 program for
Remove all subtree of Even values node in binary tree
*/
// Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode? ;
var right: TreeNode? ;
init(_ data: Int)
{
// Set node value
self.data = data;
self.left = nil;
self.right = nil;
}
}
class BinaryTree
{
var root: TreeNode? ;
init()
{
self.root = nil;
}
// Display preorder view of binary tree
func preorder(_ node: TreeNode? )
{
if (node  != nil)
{
//Print node value
print("  ", node!.data, terminator: "");
self.preorder(node!.left);
self.preorder(node!.right);
}
}
func deleteEvenSubTree(_ node: TreeNode? ) -> TreeNode?
{
if (node  != nil)
{
node!.left = self.deleteEvenSubTree(node!.left);
node!.right = self.deleteEvenSubTree(node!.right);
if (node!.left == nil &&
node!.right == nil &&
node!.data % 2 == 0)
{
// delete Node
return nil;
}
}
return node;
}
}
func main()
{
let tree1: BinaryTree = BinaryTree();
let tree2: BinaryTree = BinaryTree();
/*
1
/   \
2     7
/ \     \
6   3     8
/  \
10   12
------------
Binary tree A
*/
// Tree A
tree1.root = TreeNode(1);
tree1.root!.left = TreeNode(2);
tree1.root!.right = TreeNode(7);
tree1.root!.right!.right = TreeNode(8);
tree1.root!.left!.right = TreeNode(3);
tree1.root!.left!.left = TreeNode(6);
tree1.root!.right!.right!.left = TreeNode(10);
tree1.root!.right!.right!.right = TreeNode(12);
/*
Construct Tree number 2
---------
10
/   \
2     7
/ \     \
6   4     8
/ \
8   20
------------
Binary tree B
*/
// Tree B
tree2.root = TreeNode(10);
tree2.root!.left = TreeNode(2);
tree2.root!.right = TreeNode(7);
tree2.root!.right!.right = TreeNode(8);
tree2.root!.left!.right = TreeNode(4);
tree2.root!.left!.left = TreeNode(6);
tree2.root!.left!.right!.left = TreeNode(8);
tree2.root!.left!.right!.right = TreeNode(20);
// Test A
print("\n Before Delete Tree 1 ");
tree1.preorder(tree1.root);
// Remove subtree which contains all Even nodes
tree1.root = tree1.deleteEvenSubTree(tree1.root);
/*
1
/   \
2     7
\
3
------------
After delete Even node subtrees
*/
print("\n After Delete Tree 1 ");
tree1.preorder(tree1.root);
// Test B
print("\n Before Delete Tree 2 ");
tree2.preorder(tree2.root);
// Remove subtree which contains all Even nodes
tree2.root = tree2.deleteEvenSubTree(tree2.root);
/*
10
\
7
------------
After delete Even node subtrees
*/
print("\n After Delete Tree 2 ");
tree2.preorder(tree2.root);
}
main();``````

#### Output

`````` Before Delete Tree 1
1   2   6   3   7   8   10   12
After Delete Tree 1
1   2   3   7
Before Delete Tree 2
10   2   6   4   8   20   7   8
After Delete Tree 2
10   7``````
``````/*
Kotlin program for
Remove all subtree of Even values node in binary tree
*/
// Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode ? ;
var right: TreeNode ? ;
constructor(data: Int)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
var root: TreeNode ? ;
constructor()
{
this.root = null;
}
// Display preorder view of binary tree
fun preorder(node: TreeNode ? ): Unit
{
if (node != null)
{
//Print node value
print("  " + node.data);
this.preorder(node.left);
this.preorder(node.right);
}
}
fun deleteEvenSubTree(node: TreeNode ? ): TreeNode ?
{
if (node != null)
{
node.left = this.deleteEvenSubTree(node.left);
node.right = this.deleteEvenSubTree(node.right);
if (node.left == null &&
node.right == null &&
node.data % 2 == 0)
{
// delete Node
return null;
}
}
return node;
}
}
fun main(args: Array < String > ): Unit
{
val tree1: BinaryTree = BinaryTree();
val tree2: BinaryTree = BinaryTree();
/*
1
/   \
2     7
/ \     \
6   3     8
/  \
10   12
------------
Binary tree A
*/
// Tree A
tree1.root = TreeNode(1);
tree1.root?.left = TreeNode(2);
tree1.root?.right = TreeNode(7);
tree1.root?.right?.right = TreeNode(8);
tree1.root?.left?.right = TreeNode(3);
tree1.root?.left?.left = TreeNode(6);
tree1.root?.right?.right?.left = TreeNode(10);
tree1.root?.right?.right?.right = TreeNode(12);
/*
Construct Tree number 2
---------
10
/   \
2     7
/ \     \
6   4     8
/ \
8   20
------------
Binary tree B
*/
// Tree B
tree2.root = TreeNode(10);
tree2.root?.left = TreeNode(2);
tree2.root?.right = TreeNode(7);
tree2.root?.right?.right = TreeNode(8);
tree2.root?.left?.right = TreeNode(4);
tree2.root?.left?.left = TreeNode(6);
tree2.root?.left?.right?.left = TreeNode(8);
tree2.root?.left?.right?.right = TreeNode(20);
// Test A
print("\n Before Delete Tree 1 \n");
tree1.preorder(tree1.root);
// Remove subtree which contains all Even nodes
tree1.root = tree1.deleteEvenSubTree(tree1.root);
/*
1
/   \
2     7
\
3
------------
After delete Even node subtrees
*/
print("\n After Delete Tree 1 \n");
tree1.preorder(tree1.root);
// Test B
print("\n Before Delete Tree 2 \n");
tree2.preorder(tree2.root);
// Remove subtree which contains all Even nodes
tree2.root = tree2.deleteEvenSubTree(tree2.root);
/*
10
\
7
------------
After delete Even node subtrees
*/
print("\n After Delete Tree 2 \n");
tree2.preorder(tree2.root);
}``````

#### Output

`````` Before Delete Tree 1
1  2  6  3  7  8  10  12
After Delete Tree 1
1  2  3  7
Before Delete Tree 2
10  2  6  4  8  20  7  8
After Delete Tree 2
10  7``````

## Resultant Output Explanation

The output of the code will be the preorder traversal of the modified binary trees after removing the subtrees rooted at even value nodes.

For the provided example trees, the output will be:

Before Delete Tree 1:

``1  2  6  3  7  8  10  12``

After Delete Tree 1:

``1  2  3  7``

Before Delete Tree 2:

``10  2  6  4  8  20  7  8``

After Delete Tree 2:

``10  7``

## Time Complexity

The time complexity of the solution is proportional to the number of nodes in the binary tree since each node is visited once during the traversal. In the worst case, the time complexity is O(n), where n is the number of nodes in the binary tree.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.