Posted on by Kalkicode
Code Recursion

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_reader :data, :left, :right
	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_reader :root
	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.

New Comment