Skip to main content

Find subtree with given sum in a Binary Tree

Here given code implementation process.

/*
    C Program 
    Find subtree with given sum in a Binary Tree
*/

#include <stdio.h>
#include <stdlib.h>

//Binary Tree node
struct Node
{
	int data;
	struct Node *left, *right;
};
//This is creating a binary tree node and return new node
struct Node *get_node(int data)
{
	// Create dynamic node
	struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));
	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");
	}
	//return new node
	return new_node;
}
//Display inorder elements
void print_subtree(struct Node *node)
{
	if (node != NULL)
	{
		print_subtree(node->left);
		//Print node value
		printf("  %d", node->data);
		print_subtree(node->right);
	}
}
//Find subtree of given sum
int find_subtree(struct Node *node, int sum, struct Node **result)
{
	if (node == NULL)
	{
		return 0;
	}
	if ( *result == NULL)
	{
		// calculate the sum of left and right subtree and current node
		int k = find_subtree(node->left, sum, result) + find_subtree(node->right, sum, result) + node->data;
		if (k == sum)
		{
			*result = node;
		}
		return k;
	}
	else
	{
		return 0;
	}
}
// Handles the request to find subtree of given sum
void subtree(struct Node *root, int sum)
{
	if (root == NULL)
	{
		printf("\n Empty Tree \n");
	}
	else
	{
		struct Node *result = NULL;
		find_subtree(root, sum, & result);
		if (result == NULL)
		{
			printf("\n No subtree of sum %d\n", sum);
		}
		else
		{
			printf("\n Subtree of sum  %d are \n", sum);
			print_subtree(result);
		}
		printf("\n");
	}
}
int main()
{
	struct Node *root = NULL;
	/* Binary Tree
	-----------------------
	              5
	           /    \
	          3      -2
	         / \     / \
	        2   2   3   10
	       /   / \     /  \
	      1  -4   2   1    4
	                    
	*/
	//Add nodes
	root = get_node(5);
	root->left = get_node(3);
	root->right = get_node(-2);
	root->right->right = get_node(10);
	root->right->right->left = get_node(1);
	root->right->right->right = get_node(4);
	root->right->left = get_node(3);
	root->left->left = get_node(2);
	root->left->left->left = get_node(1);
	root->left->right = get_node(2);
	root->left->right->left = get_node(-4);
	root->left->right->right = get_node(2);
	// Test Case
	subtree(root, 0);
	subtree(root, 16);
	subtree(root, 18);
	return 0;
}

Output

 Subtree of sum  0 are
  -4  2  2

 Subtree of sum  16 are
  3  -2  1  10  4

 No subtree of sum 18

/*
    Java Program 
    Find subtree with given sum in a Binary Tree
*/

// Binary Tree node
class Node
{
	public int data;
	public Node left;
	public Node right;
	public Node(int data)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class Result
{
	public Node element;
	public Result()
	{
		this.element = null;
	}
}
//Define Binary Tree 
public class BinaryTree
{
	public Node root;
	public BinaryTree()
	{
		//Set root of tree
		this.root = null;
	}
	//Display inorder elements
	public void print_subtree(Node node)
	{
		if (node != null)
		{
			print_subtree(node.left);
			//Print node value
			System.out.print("  " + node.data);
			print_subtree(node.right);
		}
	}
	//Find subtree of given sum
	public int find_subtree(Node node, int sum, Result output)
	{
		if (node == null)
		{
			return 0;
		}
		if (output.element == null)
		{
			// calculate the sum of left and right subtree and current node
			int k = find_subtree(node.left, sum, output) + find_subtree(node.right, sum, output) + node.data;
			if (k == sum)
			{
				output.element = node;
			}
			return k;
		}
		else
		{
			return 0;
		}
	}
	// Handles the request to find subtree of given sum
	public void subtree(int sum)
	{
		if (this.root == null)
		{
			System.out.print("\n Empty Tree \n");
		}
		else
		{
			Result output = new Result();
			find_subtree(this.root, sum, output);
			if (output.element == null)
			{
				System.out.print("\n No subtree of sum " + sum + "\n");
			}
			else
			{
				System.out.print("\n Subtree of sum " + sum + " are \n");
				print_subtree(output.element);
			}
			System.out.print("\n");
		}
	}
	public static void main(String[] args)
	{
		//Create tree object
		BinaryTree tree = new BinaryTree();
		/* Binary Tree
		    -----------------------
		                  5
		               /    \
		              3      -2
		             / \     / \
		            2   2   3   10
		           /   / \     /  \
		          1  -4   2   1    4
		                        
		    */
		//Add nodes
		tree.root = new Node(5);
		tree.root.left = new Node(3);
		tree.root.right = new Node(-2);
		tree.root.right.right = new Node(10);
		tree.root.right.right.left = new Node(1);
		tree.root.right.right.right = new Node(4);
		tree.root.right.left = new Node(3);
		tree.root.left.left = new Node(2);
		tree.root.left.left.left = new Node(1);
		tree.root.left.right = new Node(2);
		tree.root.left.right.left = new Node(-4);
		tree.root.left.right.right = new Node(2);
		// Test Case
		tree.subtree(0);
		tree.subtree(16);
		tree.subtree(18);
	}
}

Output

 Subtree of sum 0 are
  -4  2  2

 Subtree of sum 16 are
  3  -2  1  10  4

 No subtree of sum 18

// Include header file
#include <iostream>

using namespace std;

//  C++ Program 
//  Find subtree with given sum in a Binary Tree

//  Binary Tree node
class Node
{
	public: 
    int data;
	Node *left;
	Node *right;
	Node(int data)
	{
		//  Set node value
		this->data = data;
		this->left = NULL;
		this->right = NULL;
	}
};
class Result
{
	public: Node *element;
	Result()
	{
		this->element = NULL;
	}
};
// Define Binary Tree
class BinaryTree
{
	public: Node *root;
	BinaryTree()
	{
		// Set root of tree
		this->root = NULL;
	}
	// Display inorder elements
	void print_subtree(Node *node)
	{
		if (node != NULL)
		{
			this->print_subtree(node->left);
			// Print node value
			cout << "  " << node->data;
			this->print_subtree(node->right);
		}
	}
	// Find subtree of given sum
	int find_subtree(Node *node, int sum, Result *output)
	{
		if (node == NULL)
		{
			return 0;
		}
		if (output->element == NULL)
		{
			//  calculate the sum of left and right subtree and current node
			int k = this->find_subtree(node->left, sum, output) + 
              this->find_subtree(node->right, sum, output) + node->data;
			if (k == sum)
			{
				output->element = node;
			}
			return k;
		}
		else
		{
			return 0;
		}
	}
	//  Handles the request to find subtree of given sum
	void subtree(int sum)
	{
		if (this->root == NULL)
		{
			cout << "\n Empty Tree \n";
		}
		else
		{
			Result *output = new Result();
			this->find_subtree(this->root, sum, output);
			if (output->element == NULL)
			{
				cout << "\n No subtree of sum " << sum << "\n";
			}
			else
			{
				cout << "\n Subtree of sum " << sum << " are \n";
				this->print_subtree(output->element);
			}
			cout << "\n";
		}
	}
};
int main()
{
	// Create tree object
	BinaryTree tree = BinaryTree();
	//  Binary Tree
	// 		    -----------------------
	// 		                  5
	// 		               /    \
	// 		              3      -2
	// 		             / \     / \
	// 		            2   2   3   10
	// 		           /   / \     /  \
	// 		          1  -4   2   1    4
	    
	// Add nodes
	tree.root = new Node(5);
	tree.root->left = new Node(3);
	tree.root->right = new Node(-2);
	tree.root->right->right = new Node(10);
	tree.root->right->right->left = new Node(1);
	tree.root->right->right->right = new Node(4);
	tree.root->right->left = new Node(3);
	tree.root->left->left = new Node(2);
	tree.root->left->left->left = new Node(1);
	tree.root->left->right = new Node(2);
	tree.root->left->right->left = new Node(-4);
	tree.root->left->right->right = new Node(2);
	//  Test Case
	tree.subtree(0);
	tree.subtree(16);
	tree.subtree(18);
	return 0;
}

Output

 Subtree of sum 0 are
  -4  2  2

 Subtree of sum 16 are
  3  -2  1  10  4

 No subtree of sum 18

// Include namespace system
using System;
//  C# Program 
//  Find subtree with given sum in a Binary Tree

//  Binary Tree node
public class Node
{
	public int data;
	public Node left;
	public Node right;
	public Node(int data)
	{
		//  Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
public class Result
{
	public Node element;
	public Result()
	{
		this.element = null;
	}
}
// Define Binary Tree
public class BinaryTree
{
	public Node root;
	public BinaryTree()
	{
		// Set root of tree
		this.root = null;
	}
	// Display inorder elements
	public void print_subtree(Node node)
	{
		if (node != null)
		{
			print_subtree(node.left);
			// Print node value
			Console.Write("  " + node.data);
			print_subtree(node.right);
		}
	}
	// Find subtree of given sum
	public int find_subtree(Node node, int sum, Result output)
	{
		if (node == null)
		{
			return 0;
		}
		if (output.element == null)
		{
			//  calculate the sum of left and right subtree and current node
			int k = find_subtree(node.left, sum, output) + find_subtree(node.right, sum, output) + node.data;
			if (k == sum)
			{
				output.element = node;
			}
			return k;
		}
		else
		{
			return 0;
		}
	}
	//  Handles the request to find subtree of given sum
	public void subtree(int sum)
	{
		if (this.root == null)
		{
			Console.Write("\n Empty Tree \n");
		}
		else
		{
			Result output = new Result();
			find_subtree(this.root, sum, output);
			if (output.element == null)
			{
				Console.Write("\n No subtree of sum " + sum + "\n");
			}
			else
			{
				Console.Write("\n Subtree of sum " + sum + " are \n");
				print_subtree(output.element);
			}
			Console.Write("\n");
		}
	}
	public static void Main(String[] args)
	{
		// Create tree object
		BinaryTree tree = new BinaryTree();
		//  Binary Tree
		// 		    -----------------------
		// 		                  5
		// 		               /    \
		// 		              3      -2
		// 		             / \     / \
		// 		            2   2   3   10
		// 		           /   / \     /  \
		// 		          1  -4   2   1    4
		// 		                        
		// 		    
		// Add nodes
		tree.root = new Node(5);
		tree.root.left = new Node(3);
		tree.root.right = new Node(-2);
		tree.root.right.right = new Node(10);
		tree.root.right.right.left = new Node(1);
		tree.root.right.right.right = new Node(4);
		tree.root.right.left = new Node(3);
		tree.root.left.left = new Node(2);
		tree.root.left.left.left = new Node(1);
		tree.root.left.right = new Node(2);
		tree.root.left.right.left = new Node(-4);
		tree.root.left.right.right = new Node(2);
		//  Test Case
		tree.subtree(0);
		tree.subtree(16);
		tree.subtree(18);
	}
}

Output

 Subtree of sum 0 are
  -4  2  2

 Subtree of sum 16 are
  3  -2  1  10  4

 No subtree of sum 18

<?php
//  Php Program 
//  Find subtree with given sum in a Binary Tree

//  Binary Tree node
class Node
{
	public $data;
	public $left;
	public $right;

	function __construct($data)
	{
		//  Set node value
		$this->data = $data;
		$this->left = null;
		$this->right = null;
	}
}
class Result
{
	public $element;

	function __construct()
	{
		$this->element = null;
	}
}
// Define Binary Tree
class BinaryTree
{
	public $root;

	function __construct()
	{
		// Set root of tree
		$this->root = null;
	}
	// Display inorder elements
	public	function print_subtree($node)
	{
		if ($node != null)
		{
			$this->print_subtree($node->left);
			// Print node value
			echo "  ". $node->data;
			$this->print_subtree($node->right);
		}
	}
	// Find subtree of given sum
	public	function find_subtree($node, $sum, $output)
	{
		if ($node == null)
		{
			return 0;
		}
		if ($output->element == null)
		{
			//  calculate the sum of left and right subtree and current node
			$k = $this->find_subtree($node->left, $sum, $output) + $this->find_subtree($node->right, $sum, $output) + $node->data;
			if ($k == $sum)
			{
				$output->element = $node;
			}
			return $k;
		}
		else
		{
			return 0;
		}
	}
	//  Handles the request to find subtree of given sum
	public	function subtree($sum)
	{
		if ($this->root == null)
		{
			echo "\n Empty Tree \n";
		}
		else
		{
			$output = new Result();
			$this->find_subtree($this->root, $sum, $output);
			if ($output->element == null)
			{
				echo "\n No subtree of sum ". $sum ."\n";
			}
			else
			{
				echo "\n Subtree of sum ". $sum ." are \n";
				$this->print_subtree($output->element);
			}
			echo "\n";
		}
	}
}

function main()
{
	// Create tree object
	$tree = new BinaryTree();
	//  Binary Tree
	// 		    -----------------------
	// 		                  5
	// 		               /    \
	// 		              3      -2
	// 		             / \     / \
	// 		            2   2   3   10
	// 		           /   / \     /  \
	// 		          1  -4   2   1    4
	// 		                        
	// 		    
	// Add nodes
	$tree->root = new Node(5);
	$tree->root->left = new Node(3);
	$tree->root->right = new Node(-2);
	$tree->root->right->right = new Node(10);
	$tree->root->right->right->left = new Node(1);
	$tree->root->right->right->right = new Node(4);
	$tree->root->right->left = new Node(3);
	$tree->root->left->left = new Node(2);
	$tree->root->left->left->left = new Node(1);
	$tree->root->left->right = new Node(2);
	$tree->root->left->right->left = new Node(-4);
	$tree->root->left->right->right = new Node(2);
	//  Test Case
	$tree->subtree(0);
	$tree->subtree(16);
	$tree->subtree(18);
}
main();

Output

 Subtree of sum 0 are
  -4  2  2

 Subtree of sum 16 are
  3  -2  1  10  4

 No subtree of sum 18

//  Node Js Program 
//  Find subtree with given sum in a Binary Tree

//  Binary Tree node
class Node
{
	constructor(data)
	{
		//  Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class Result
{
	constructor()
	{
		this.element = null;
	}
}
// Define Binary Tree
class BinaryTree
{
	constructor()
	{
		// Set root of tree
		this.root = null;
	}
	// Display inorder elements
	print_subtree(node)
	{
		if (node != null)
		{
			this.print_subtree(node.left);
			// Print node value
			process.stdout.write("  " + node.data);
			this.print_subtree(node.right);
		}
	}
	// Find subtree of given sum
	find_subtree(node, sum, output)
	{
		if (node == null)
		{
			return 0;
		}
		if (output.element == null)
		{
			//  calculate the sum of left and right subtree and current node
			var k = this.find_subtree(node.left, sum, output) + this.find_subtree(node.right, sum, output) + node.data;
			if (k == sum)
			{
				output.element = node;
			}
			return k;
		}
		else
		{
			return 0;
		}
	}
	//  Handles the request to find subtree of given sum
	subtree(sum)
	{
		if (this.root == null)
		{
			process.stdout.write("\n Empty Tree \n");
		}
		else
		{
			var output = new Result();
			this.find_subtree(this.root, sum, output);
			if (output.element == null)
			{
				process.stdout.write("\n No subtree of sum " + sum + "\n");
			}
			else
			{
				process.stdout.write("\n Subtree of sum " + sum + " are \n");
				this.print_subtree(output.element);
			}
			process.stdout.write("\n");
		}
	}
}

function main()
{
	// Create tree object
	var tree = new BinaryTree();
	//  Binary Tree
	// 		    -----------------------
	// 		                  5
	// 		               /    \
	// 		              3      -2
	// 		             / \     / \
	// 		            2   2   3   10
	// 		           /   / \     /  \
	// 		          1  -4   2   1    4
	// 		                        
	// 		    
	// Add nodes
	tree.root = new Node(5);
	tree.root.left = new Node(3);
	tree.root.right = new Node(-2);
	tree.root.right.right = new Node(10);
	tree.root.right.right.left = new Node(1);
	tree.root.right.right.right = new Node(4);
	tree.root.right.left = new Node(3);
	tree.root.left.left = new Node(2);
	tree.root.left.left.left = new Node(1);
	tree.root.left.right = new Node(2);
	tree.root.left.right.left = new Node(-4);
	tree.root.left.right.right = new Node(2);
	//  Test Case
	tree.subtree(0);
	tree.subtree(16);
	tree.subtree(18);
}
main();

Output

 Subtree of sum 0 are
  -4  2  2

 Subtree of sum 16 are
  3  -2  1  10  4

 No subtree of sum 18

#  Python 3 Program 
#  Find subtree with given sum in a Binary Tree

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

class Result :
	
	def __init__(self) :
		self.element = None
	

# Define Binary Tree 
class BinaryTree :
	
	def __init__(self) :
		# Set root of tree
		self.root = None
	
	# Display inorder elements
	def print_subtree(self, node) :
		if (node != None) :
			self.print_subtree(node.left)
			# Print node value
			print("  ", node.data, end = "")
			self.print_subtree(node.right)
		
	
	# Find subtree of given sum
	def find_subtree(self, node, sum, output) :
		if (node == None) :
			return 0
		
		if (output.element == None) :
			#  calculate the sum of left and right subtree and current node
			k = self.find_subtree(node.left, sum, output) + self.find_subtree(node.right, sum, output) + node.data
			if (k == sum) :
				output.element = node
			
			return k
		else :
			return 0
		
	
	#  Handles the request to find subtree of given sum
	def subtree(self, sum) :
		if (self.root == None) :
			print("\n Empty Tree \n", end = "")
		else :
			output = Result()
			self.find_subtree(self.root, sum, output)
			if (output.element == None) :
				print("\n No subtree of sum ", sum ,"\n", end = "")
			else :
				print("\n Subtree of sum ", sum ," are \n", end = "")
				self.print_subtree(output.element)
			
			print("\n", end = "")
		
	

def main() :
	# Create tree object
	tree = BinaryTree()
	#  Binary Tree
	# 		    -----------------------
	# 		                  5
	# 		               /    \
	# 		              3      -2
	# 		             / \     / \
	# 		            2   2   3   10
	# 		           /   / \     /  \
	# 		          1  -4   2   1    4
	# 		                        
	# 		    
	
	# Add nodes
	tree.root = Node(5)
	tree.root.left = Node(3)
	tree.root.right = Node(-2)
	tree.root.right.right = Node(10)
	tree.root.right.right.left = Node(1)
	tree.root.right.right.right = Node(4)
	tree.root.right.left = Node(3)
	tree.root.left.left = Node(2)
	tree.root.left.left.left = Node(1)
	tree.root.left.right = Node(2)
	tree.root.left.right.left = Node(-4)
	tree.root.left.right.right = Node(2)
	#  Test Case
	tree.subtree(0)
	tree.subtree(16)
	tree.subtree(18)

if __name__ == "__main__": main()

Output

 Subtree of sum  0  are
   -4   2   2

 Subtree of sum  16  are
   3   -2   1   10   4

 No subtree of sum  18

#     Ruby Program 
#     Find subtree with given sum in a Binary Tree

#  Binary Tree node
class Node  
	# Define the accessor and reader of class Node  
	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 Result  
	# Define the accessor and reader of class Result  
	attr_reader :element
	attr_accessor :element
 
	
	def initialize() 
		self.element = nil
	end

end

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

	# Display inorder elements
	def print_subtree(node) 
		if (node != nil) 
			self.print_subtree(node.left)
			# Print node value
			print("  ", node.data)
			self.print_subtree(node.right)
		end

	end

	# Find subtree of given sum
	def find_subtree(node, sum, output) 
		if (node == nil) 
			return 0
		end

		if (output.element == nil) 
			#  calculate the sum of left and right subtree and current node
			k = self.find_subtree(node.left, sum, output) + self.find_subtree(node.right, sum, output) + node.data
			if (k == sum) 
				output.element = node
			end

			return k
		else 
			return 0
		end

	end

	#  Handles the request to find subtree of given sum
	def subtree(sum) 
		if (self.root == nil) 
			print("\n Empty Tree \n")
		else 
			output = Result.new()
			self.find_subtree(self.root, sum, output)
			if (output.element == nil) 
				print("\n No subtree of sum ", sum ,"\n")
			else 
				print("\n Subtree of sum ", sum ," are \n")
				self.print_subtree(output.element)
			end

			print("\n")
		end

	end

end

def main() 
	# Create tree object
	tree = BinaryTree.new()
	#  Binary Tree
	# 		    -----------------------
	# 		                  5
	# 		               /    \
	# 		              3      -2
	# 		             / \     / \
	# 		            2   2   3   10
	# 		           /   / \     /  \
	# 		          1  -4   2   1    4
	# 		                        
	# 		    
	
	# Add nodes
	tree.root = Node.new(5)
	tree.root.left = Node.new(3)
	tree.root.right = Node.new(-2)
	tree.root.right.right = Node.new(10)
	tree.root.right.right.left = Node.new(1)
	tree.root.right.right.right = Node.new(4)
	tree.root.right.left = Node.new(3)
	tree.root.left.left = Node.new(2)
	tree.root.left.left.left = Node.new(1)
	tree.root.left.right = Node.new(2)
	tree.root.left.right.left = Node.new(-4)
	tree.root.left.right.right = Node.new(2)
	#  Test Case
	tree.subtree(0)
	tree.subtree(16)
	tree.subtree(18)
end

main()

Output

 Subtree of sum 0 are 
  -4  2  2

 Subtree of sum 16 are 
  3  -2  1  10  4

 No subtree of sum 18


//  Scala Program 
//  Find subtree with given sum in a Binary Tree

//  Binary Tree node
class Node(var data: Int , var left: Node , var right: Node)
{
	def this(data: Int)
	{
		this(data, null, null);
	}
}
class Result(var element: Node)
{
	def this()
	{
		this(null);
	}
}
// Define Binary Tree
class BinaryTree(var root: Node)
{
	def this()
	{
		this(null);
	}
	// Display inorder elements
	def print_subtree(node: Node): Unit = {
		if (node != null)
		{
			print_subtree(node.left);
			// Print node value
			print("  " + node.data);
			print_subtree(node.right);
		}
	}
	// Find subtree of given sum
	def find_subtree(node: Node, sum: Int, output: Result): Int = {
		if (node == null)
		{
			return 0;
		}
		if (output.element == null)
		{
			//  calculate the sum of left and right subtree and current node
			var k: Int = find_subtree(node.left, sum, output) + find_subtree(node.right, sum, output) + node.data;
			if (k == sum)
			{
				output.element = node;
			}
			return k;
		}
		else
		{
			return 0;
		}
	}
	//  Handles the request to find subtree of given sum
	def subtree(sum: Int): Unit = {
		if (this.root == null)
		{
			print("\n Empty Tree \n");
		}
		else
		{
			var output: Result = new Result();
			find_subtree(this.root, sum, output);
			if (output.element == null)
			{
				print("\n No subtree of sum " + sum + "\n");
			}
			else
			{
				print("\n Subtree of sum " + sum + " are \n");
				print_subtree(output.element);
			}
			print("\n");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		// Create tree object
		var tree: BinaryTree = new BinaryTree();
		//  Binary Tree
		// 		    -----------------------
		// 		                  5
		// 		               /    \
		// 		              3      -2
		// 		             / \     / \
		// 		            2   2   3   10
		// 		           /   / \     /  \
		// 		          1  -4   2   1    4
		// 		                        
		// 		    
		// Add nodes
		tree.root = new Node(5);
		tree.root.left = new Node(3);
		tree.root.right = new Node(-2);
		tree.root.right.right = new Node(10);
		tree.root.right.right.left = new Node(1);
		tree.root.right.right.right = new Node(4);
		tree.root.right.left = new Node(3);
		tree.root.left.left = new Node(2);
		tree.root.left.left.left = new Node(1);
		tree.root.left.right = new Node(2);
		tree.root.left.right.left = new Node(-4);
		tree.root.left.right.right = new Node(2);
		//  Test Case
		tree.subtree(0);
		tree.subtree(16);
		tree.subtree(18);
	}
}

Output

 Subtree of sum 0 are
  -4  2  2

 Subtree of sum 16 are
  3  -2  1  10  4

 No subtree of sum 18

//  Swift 4 Program 
//  Find subtree with given sum in a Binary Tree

//  Binary Tree node
class Node
{
	var data: Int;
	var left: Node? ;
	var right: Node? ;
	init(_ data: Int)
	{
		//  Set node value
		self.data = data;
		self.left = nil;
		self.right = nil;
	}
}
class Result
{
	var element: Node? ;
	init()
	{
		self.element = nil;
	}
}
// Define Binary Tree
class BinaryTree
{
	var root: Node? ;
	init()
	{
		// Set root of tree
		self.root = nil;
	}
	// Display inorder elements
	func print_subtree(_ node: Node? )
	{
		if (node != nil)
		{
			self.print_subtree(node!.left);
			// Print node value
			print("  ", node!.data, terminator: "");
			self.print_subtree(node!.right);
		}
	}
	// Find subtree of given sum
	func find_subtree(_ node: Node? , _ sum : Int, _ output: Result? )->Int
	{
		if (node == nil)
		{
			return 0;
		}
		if (output!.element == nil)
		{
			//  calculate the sum of left and right subtree and current node
			let k: Int = self.find_subtree(node!.left, sum, output) + self.find_subtree(node!.right, sum, output) + node!.data;
			if (k == sum)
			{
				output!.element = node;
			}
			return k;
		}
		else
		{
			return 0;
		}
	}
	//  Handles the request to find subtree of given sum
	func subtree(_ sum: Int)
	{
		if (self.root == nil)
		{
			print("\n Empty Tree \n", terminator: "");
		}
		else
		{
			let output: Result? = Result();
			let _ = self.find_subtree(self.root, sum, output);
			if (output!.element == nil)
			{
				print("\n No subtree of sum ", sum ,"\n", terminator: "");
			}
			else
			{
				print("\n Subtree of sum ", sum ," are \n", terminator: "");
				self.print_subtree(output!.element);
			}
			print("\n", terminator: "");
		}
	}
}
func main()
{
	// Create tree object
	let tree: BinaryTree = BinaryTree();
	//  Binary Tree
	// 		    -----------------------
	// 		                  5
	// 		               /    \
	// 		              3      -2
	// 		             / \     / \
	// 		            2   2   3   10
	// 		           /   / \     /  \
	// 		          1  -4   2   1    4
	// 		                        
	// 		    
	// Add nodes
	tree.root = Node(5);
	tree.root!.left = Node(3);
	tree.root!.right = Node(-2);
	tree.root!.right!.right = Node(10);
	tree.root!.right!.right!.left = Node(1);
	tree.root!.right!.right!.right = Node(4);
	tree.root!.right!.left = Node(3);
	tree.root!.left!.left = Node(2);
	tree.root!.left!.left!.left = Node(1);
	tree.root!.left!.right = Node(2);
	tree.root!.left!.right!.left = Node(-4);
	tree.root!.left!.right!.right = Node(2);
	//  Test Case
	tree.subtree(0);
	tree.subtree(16);
	tree.subtree(18);
}
main();

Output

 Subtree of sum  0  are
   -4   2   2

 Subtree of sum  16  are
   3   -2   1   10   4

 No subtree of sum  18
Last updated on by Kalkicode




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