Skip to main content

Root to leaf path sum equal to a given number

Here given code implementation process.

/*
    C Program 
    Root to leaf path sum equal to a given number
*/
#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 pre order elements
void print_preorder(struct Node *node)
{
	if (node != NULL)
	{
		//Print node value
		printf("  %d", node->data);
		print_preorder(node->left);
		print_preorder(node->right);
	}
}
//Check whether the path of leaf nodes from the root is equal to the given sum?
int find_path_sum(struct Node *node, int sum, int k)
{
	if (node == NULL)
	{
		return 0;
	}
	if (node->left == NULL && node->right == NULL && k + node->data == sum)
	{
		// When current node is leaf node and path is equal to given sum
		return 1;
	}
	//Recursively executing left and right subtree
	if (find_path_sum(node->left, sum, node->data + k) || find_path_sum(node->right, sum, node->data + k))
	{
		return 1;
	}
	else
	{
		return 0;
	}
}
// Handles the request to find the sum exist in path from root to leaf nodes
void check_sum_path(struct Node *root, int sum)
{
	if (root == NULL)
	{
		printf("\n Empty Tree \n");
		return;
	}
	if (find_path_sum(root, sum, 0))
	{
		printf("\n Path from root to leaf of [%d] sum exists", sum);
	}
	else
	{
		printf("\n Path from root to leaf of [%d] sum are not exists", sum);
	}
}
int main()
{
	// Define pointer
	struct Node *root = NULL;
	/* 
	     3
	    /  \
	   /    \
	  2      1
	   \    /  \
	    1  5    6
	   / \
	  8   7
	-----------------------
	Binary Tree
	*/
	root = get_node(3);
	root->left = get_node(2);
	root->left->right = get_node(1);
	root->right = get_node(1);
	root->right->right = get_node(6);
	root->right->left = get_node(5);
	root->left->right->left = get_node(8);
	root->left->right->right = get_node(7);
	printf("\n Tree Node : \n");
	print_preorder(root);
	// Test Cases
	check_sum_path(root, 9);
	check_sum_path(root, 13);
	check_sum_path(root, 15);
	return 0;
}

Output

 Tree Node :
  3  2  1  8  7  1  5  6
 Path from root to leaf of [9] sum exists
 Path from root to leaf of [13] sum exists
 Path from root to leaf of [15] sum are not exists
/*
    Java Program 
    Root to leaf path sum equal to a given number
*/
// 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;
	}
}
//Define Binary Tree 
public class BinaryTree
{
	public Node root;
	public BinaryTree()
	{
		//Set root of tree
		this.root = null;
	}
	//Display pre order elements
	public void print_preorder(Node node)
	{
		if (node != null)
		{
			//Print node value
			System.out.print("   " + node.data);
			print_preorder(node.left);
			print_preorder(node.right);
		}
	}
	// Check whether the path of leaf nodes from the root is equal to the given sum?
	public boolean find_path_sum(Node node, int sum, int k)
	{
		if (node == null)
		{
			return false;
		}
		if (node.left == null && node.right == null && k + node.data == sum)
		{
			// When current node is leaf node and path is equal to given sum
			return true;
		}
		// Recursively executing left and right subtree
		if (find_path_sum(node.left, sum, node.data + k) 
            || find_path_sum(node.right, sum, node.data + k))
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	// Handles the request to find the sum exist in path from root to leaf nodes
	public void check_sum_path(int sum)
	{
		if (this.root == null)
		{
			System.out.print("\n Empty Tree \n");
			return;
		}
		if (find_path_sum(this.root, sum, 0))
		{
			System.out.print("\n Path from root to leaf of [" + sum + "] sum exists");
		}
		else
		{
			System.out.print("\n Path from root to leaf of [" + sum + "] sum are not exists");
		}
	}
	public static void main(String[] args)
	{
		//Create tree object
		BinaryTree tree = new BinaryTree();
		/* 
		     3
		    /  \
		   /    \
		  2      1
		   \    /  \
		    1  5    6
		   / \
		  8   7
		-----------------------
		Binary Tree
		*/
		tree.root = new Node(3);
		tree.root.left = new Node(2);
		tree.root.left.right = new Node(1);
		tree.root.right = new Node(1);
		tree.root.right.right = new Node(6);
		tree.root.right.left = new Node(5);
		tree.root.left.right.left = new Node(8);
		tree.root.left.right.right = new Node(7);
		System.out.print("\n Tree Node : \n");
		tree.print_preorder(tree.root);
		// Test Cases
		tree.check_sum_path(9);
		tree.check_sum_path(13);
		tree.check_sum_path(15);
	}
}

Output

 Tree Node :
   3   2   1   8   7   1   5   6
 Path from root to leaf of [9] sum exists
 Path from root to leaf of [13] sum exists
 Path from root to leaf of [15] sum are not exists
// Include header file
#include <iostream>
using namespace std;

/*
    C++ Program 
    Root to leaf path sum equal to a given number
*/

//  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;
	}
};
// Define Binary Tree
class BinaryTree
{
	public: Node *root;
	BinaryTree()
	{
		// Set root of tree
		this->root = NULL;
	}
	// Display pre order elements
	void print_preorder(Node *node)
	{
		if (node != NULL)
		{
			// Print node value
			cout << "   " << node->data;
			this->print_preorder(node->left);
			this->print_preorder(node->right);
		}
	}
	//  Check whether the path of leaf nodes from the root is equal to the given sum?
	bool find_path_sum(Node *node, int sum, int k)
	{
		if (node == NULL)
		{
			return false;
		}
		if (node->left == NULL && node->right == NULL && k + node->data == sum)
		{
			//  When current node is leaf node and path is equal to given sum
			return true;
		}
		//  Recursively executing left and right subtree
		if (this->find_path_sum(node->left, sum, node->data + k) || this->find_path_sum(node->right, sum, node->data + k))
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	//  Handles the request to find the sum exist in path from root to leaf nodes
	void check_sum_path(int sum)
	{
		if (this->root == NULL)
		{
			cout << "\n Empty Tree \n";
			return;
		}
		if (this->find_path_sum(this->root, sum, 0))
		{
			cout << "\n Path from root to leaf of [" << sum << "] sum exists";
		}
		else
		{
			cout << "\n Path from root to leaf of [" << sum << "] sum are not exists";
		}
	}
};
int main()
{
	// Create tree object
	BinaryTree tree = BinaryTree();
	/*
			     3
			    /  \
			   /    \
			  2      1
			   \    /  \
			    1  5    6
			   / \
			  8   7
			-----------------------
			Binary Tree
			*/
	tree.root = new Node(3);
	tree.root->left = new Node(2);
	tree.root->left->right = new Node(1);
	tree.root->right = new Node(1);
	tree.root->right->right = new Node(6);
	tree.root->right->left = new Node(5);
	tree.root->left->right->left = new Node(8);
	tree.root->left->right->right = new Node(7);
	cout << "\n Tree Node : \n";
	tree.print_preorder(tree.root);
	//  Test Cases
	tree.check_sum_path(9);
	tree.check_sum_path(13);
	tree.check_sum_path(15);
	return 0;
}

Output

 Tree Node :
   3   2   1   8   7   1   5   6
 Path from root to leaf of [9] sum exists
 Path from root to leaf of [13] sum exists
 Path from root to leaf of [15] sum are not exists
// Include namespace system
using System;

/*
    C# Program 
    Root to leaf path sum equal to a given number
*/

//  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;
	}
}
// Define Binary Tree
public class BinaryTree
{
	public Node root;
	public BinaryTree()
	{
		// Set root of tree
		this.root = null;
	}
	// Display pre order elements
	public void print_preorder(Node node)
	{
		if (node != null)
		{
			// Print node value
			Console.Write("   " + node.data);
			print_preorder(node.left);
			print_preorder(node.right);
		}
	}
	//  Check whether the path of leaf nodes from the root is equal to the given sum?
	public Boolean find_path_sum(Node node, int sum, int k)
	{
		if (node == null)
		{
			return false;
		}
		if (node.left == null && node.right == null && k + node.data == sum)
		{
			//  When current node is leaf node and path is equal to given sum
			return true;
		}
		//  Recursively executing left and right subtree
		if (find_path_sum(node.left, sum, node.data + k) || find_path_sum(node.right, sum, node.data + k))
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	//  Handles the request to find the sum exist in path from root to leaf nodes
	public void check_sum_path(int sum)
	{
		if (this.root == null)
		{
			Console.Write("\n Empty Tree \n");
			return;
		}
		if (find_path_sum(this.root, sum, 0))
		{
			Console.Write("\n Path from root to leaf of [" + sum + "] sum exists");
		}
		else
		{
			Console.Write("\n Path from root to leaf of [" + sum + "] sum are not exists");
		}
	}
	public static void Main(String[] args)
	{
		// Create tree object
		BinaryTree tree = new BinaryTree();
		/* 
				     3
				    /  \
				   /    \
				  2      1
				   \    /  \
				    1  5    6
				   / \
				  8   7
				-----------------------
				Binary Tree
				*/
		tree.root = new Node(3);
		tree.root.left = new Node(2);
		tree.root.left.right = new Node(1);
		tree.root.right = new Node(1);
		tree.root.right.right = new Node(6);
		tree.root.right.left = new Node(5);
		tree.root.left.right.left = new Node(8);
		tree.root.left.right.right = new Node(7);
		Console.Write("\n Tree Node : \n");
		tree.print_preorder(tree.root);
		//  Test Cases
		tree.check_sum_path(9);
		tree.check_sum_path(13);
		tree.check_sum_path(15);
	}
}

Output

 Tree Node :
   3   2   1   8   7   1   5   6
 Path from root to leaf of [9] sum exists
 Path from root to leaf of [13] sum exists
 Path from root to leaf of [15] sum are not exists
<?php
/*
    Php Program 
    Root to leaf path sum equal to a given number
*/

//  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;
	}
}
// Define Binary Tree
class BinaryTree
{
	public $root;

	function __construct()
	{
		// Set root of tree
		$this->root = null;
	}
	// Display pre order elements
	public	function print_preorder($node)
	{
		if ($node != null)
		{
			// Print node value
			echo "   ". $node->data;
			$this->print_preorder($node->left);
			$this->print_preorder($node->right);
		}
	}
	//  Check whether the path of leaf nodes from the root is equal to the given sum?
	public	function find_path_sum($node, $sum, $k)
	{
		if ($node == null)
		{
			return false;
		}
		if ($node->left == null && $node->right == null && $k + $node->data == $sum)
		{
			//  When current node is leaf node and path is equal to given sum
			return true;
		}
		//  Recursively executing left and right subtree
		if ($this->find_path_sum($node->left, $sum, $node->data + $k) || $this->find_path_sum($node->right, $sum, $node->data + $k))
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	//  Handles the request to find the sum exist in path from root to leaf nodes
	public	function check_sum_path($sum)
	{
		if ($this->root == null)
		{
			echo "\n Empty Tree \n";
			return;
		}
		if ($this->find_path_sum($this->root, $sum, 0))
		{
			echo "\n Path from root to leaf of [". $sum ."] sum exists";
		}
		else
		{
			echo "\n Path from root to leaf of [". $sum ."] sum are not exists";
		}
	}
}

function main()
{
	// Create tree object
	$tree = new BinaryTree();
	/* 
			     3
			    /  \
			   /    \
			  2      1
			   \    /  \
			    1  5    6
			   / \
			  8   7
			-----------------------
			Binary Tree
			*/
	$tree->root = new Node(3);
	$tree->root->left = new Node(2);
	$tree->root->left->right = new Node(1);
	$tree->root->right = new Node(1);
	$tree->root->right->right = new Node(6);
	$tree->root->right->left = new Node(5);
	$tree->root->left->right->left = new Node(8);
	$tree->root->left->right->right = new Node(7);
	echo "\n Tree Node : \n";
	$tree->print_preorder($tree->root);
	//  Test Cases
	$tree->check_sum_path(9);
	$tree->check_sum_path(13);
	$tree->check_sum_path(15);
}
main();

Output

 Tree Node :
   3   2   1   8   7   1   5   6
 Path from root to leaf of [9] sum exists
 Path from root to leaf of [13] sum exists
 Path from root to leaf of [15] sum are not exists
/*
    Node Js Program 
    Root to leaf path sum equal to a given number
*/

//  Binary Tree node
class Node
{
	constructor(data)
	{
		//  Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
// Define Binary Tree
class BinaryTree
{
	constructor()
	{
		// Set root of tree
		this.root = null;
	}
	// Display pre order elements
	print_preorder(node)
	{
		if (node != null)
		{
			// Print node value
			process.stdout.write("   " + node.data);
			this.print_preorder(node.left);
			this.print_preorder(node.right);
		}
	}
	//  Check whether the path of leaf nodes from the root is equal to the given sum?
	find_path_sum(node, sum, k)
	{
		if (node == null)
		{
			return false;
		}
		if (node.left == null && node.right == null && k + node.data == sum)
		{
			//  When current node is leaf node and path is equal to given sum
			return true;
		}
		//  Recursively executing left and right subtree
		if (this.find_path_sum(node.left, sum, node.data + k) || this.find_path_sum(node.right, sum, node.data + k))
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	//  Handles the request to find the sum exist in path from root to leaf nodes
	check_sum_path(sum)
	{
		if (this.root == null)
		{
			process.stdout.write("\n Empty Tree \n");
			return;
		}
		if (this.find_path_sum(this.root, sum, 0))
		{
			process.stdout.write("\n Path from root to leaf of [" + sum + "] sum exists");
		}
		else
		{
			process.stdout.write("\n Path from root to leaf of [" + sum + "] sum are not exists");
		}
	}
}

function main()
{
	// Create tree object
	var tree = new BinaryTree();
	/* 
			     3
			    /  \
			   /    \
			  2      1
			   \    /  \
			    1  5    6
			   / \
			  8   7
			-----------------------
			Binary Tree
	*/
	tree.root = new Node(3);
	tree.root.left = new Node(2);
	tree.root.left.right = new Node(1);
	tree.root.right = new Node(1);
	tree.root.right.right = new Node(6);
	tree.root.right.left = new Node(5);
	tree.root.left.right.left = new Node(8);
	tree.root.left.right.right = new Node(7);
	process.stdout.write("\n Tree Node : \n");
	tree.print_preorder(tree.root);
	//  Test Cases
	tree.check_sum_path(9);
	tree.check_sum_path(13);
	tree.check_sum_path(15);
}
main();

Output

 Tree Node :
   3   2   1   8   7   1   5   6
 Path from root to leaf of [9] sum exists
 Path from root to leaf of [13] sum exists
 Path from root to leaf of [15] sum are not exists
#  Python 3 Program 
#  Root to leaf path sum equal to a given number

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

# Define Binary Tree 
class BinaryTree :
	
	def __init__(self) :
		# Set root of tree
		self.root = None
	
	# Display pre order elements
	def print_preorder(self, node) :
		if (node != None) :
			# Print node value
			print("   ", node.data, end = "")
			self.print_preorder(node.left)
			self.print_preorder(node.right)
		
	
	#  Check whether the path of leaf nodes from the root is equal to the given sum?
	def find_path_sum(self, node, sum, k) :
		if (node == None) :
			return False
		
		if (node.left == None and node.right == None and k + node.data == sum) :
			#  When current node is leaf node and path is equal to given sum
			return True
		
		#  Recursively executing left and right subtree
		if (self.find_path_sum(node.left, sum, node.data + k) or self.find_path_sum(node.right, sum, node.data + k)) :
			return True
		else :
			return False
		
	
	#  Handles the request to find the sum exist in path from root to leaf nodes
	def check_sum_path(self, sum) :
		if (self.root == None) :
			print("\n Empty Tree \n", end = "")
			return
		
		if (self.find_path_sum(self.root, sum, 0)) :
			print("\n Path from root to leaf of [", sum ,"] sum exists", end = "")
		else :
			print("\n Path from root to leaf of [", sum ,"] sum are not exists", end = "")
		
	

def main() :
	# Create tree object
	tree = BinaryTree()
	#  
	# 		     3
	# 		    /  \
	# 		   /    \
	# 		  2      1
	# 		   \    /  \
	# 		    1  5    6
	# 		   / \
	# 		  8   7
	# 		-----------------------
	# 		Binary Tree
	# 		
	
	tree.root = Node(3)
	tree.root.left = Node(2)
	tree.root.left.right = Node(1)
	tree.root.right = Node(1)
	tree.root.right.right = Node(6)
	tree.root.right.left = Node(5)
	tree.root.left.right.left = Node(8)
	tree.root.left.right.right = Node(7)
	print("\n Tree Node : \n", end = "")
	tree.print_preorder(tree.root)
	#  Test Cases
	tree.check_sum_path(9)
	tree.check_sum_path(13)
	tree.check_sum_path(15)

if __name__ == "__main__": main()

Output

 Tree Node :
    3    2    1    8    7    1    5    6
 Path from root to leaf of [ 9 ] sum exists
 Path from root to leaf of [ 13 ] sum exists
 Path from root to leaf of [ 15 ] sum are not exists
#  Ruby Program 
#  Root to leaf path sum equal to a given number

#  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

# 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 pre order elements
	def print_preorder(node) 
		if (node != nil) 
			# Print node value
			print("   ", node.data)
			self.print_preorder(node.left)
			self.print_preorder(node.right)
		end

	end

	#  Check whether the path of leaf nodes from the root is equal to the given sum?
	def find_path_sum(node, sum, k) 
		if (node == nil) 
			return false
		end

		if (node.left == nil && node.right == nil && k + node.data == sum) 
			#  When current node is leaf node and path is equal to given sum
			return true
		end

		#  Recursively executing left and right subtree
		if (self.find_path_sum(node.left, sum, node.data + k) || self.find_path_sum(node.right, sum, node.data + k)) 
			return true
		else 
			return false
		end

	end

	#  Handles the request to find the sum exist in path from root to leaf nodes
	def check_sum_path(sum) 
		if (self.root == nil) 
			print("\n Empty Tree \n")
			return
		end

		if (self.find_path_sum(self.root, sum, 0)) 
			print("\n Path from root to leaf of [", sum ,"] sum exists")
		else 
			print("\n Path from root to leaf of [", sum ,"] sum are not exists")
		end

	end

end

def main() 
	# Create tree object
	tree = BinaryTree.new()
	#  
	# 		     3
	# 		    /  \
	# 		   /    \
	# 		  2      1
	# 		   \    /  \
	# 		    1  5    6
	# 		   / \
	# 		  8   7
	# 		-----------------------
	# 		Binary Tree
	# 		
	
	tree.root = Node.new(3)
	tree.root.left = Node.new(2)
	tree.root.left.right = Node.new(1)
	tree.root.right = Node.new(1)
	tree.root.right.right = Node.new(6)
	tree.root.right.left = Node.new(5)
	tree.root.left.right.left = Node.new(8)
	tree.root.left.right.right = Node.new(7)
	print("\n Tree Node : \n")
	tree.print_preorder(tree.root)
	#  Test Cases
	tree.check_sum_path(9)
	tree.check_sum_path(13)
	tree.check_sum_path(15)
end

main()

Output

 Tree Node : 
   3   2   1   8   7   1   5   6
 Path from root to leaf of [9] sum exists
 Path from root to leaf of [13] sum exists
 Path from root to leaf of [15] sum are not exists
/*
    Scala Program 
    Root to leaf path sum equal to a given number
*/

//  Binary Tree node
class Node(var data: Int , var left: Node , var right: Node)
{
	def this(data: Int)
	{
		this(data, null, null);
	}
}
// Define Binary Tree
class BinaryTree(var root: Node)
{
	def this()
	{
		this(null);
	}
	// Display pre order elements
	def print_preorder(node: Node): Unit = {
		if (node != null)
		{
			// Print node value
			print("   " + node.data);
			print_preorder(node.left);
			print_preorder(node.right);
		}
	}
	//  Check whether the path of leaf nodes from the root is equal to the given sum?
	def find_path_sum(node: Node, sum: Int, k: Int): Boolean = {
		if (node == null)
		{
			return false;
		}
		if (node.left == null && node.right == null && k + node.data == sum)
		{
			//  When current node is leaf node and path is equal to given sum
			return true;
		}
		//  Recursively executing left and right subtree
		if (find_path_sum(node.left, sum, node.data + k) || find_path_sum(node.right, sum, node.data + k))
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	//  Handles the request to find the sum exist in path from root to leaf nodes
	def check_sum_path(sum: Int): Unit = {
		if (this.root == null)
		{
			print("\n Empty Tree \n");
			return;
		}
		if (find_path_sum(this.root, sum, 0))
		{
			print("\n Path from root to leaf of [" + sum + "] sum exists");
		}
		else
		{
			print("\n Path from root to leaf of [" + sum + "] sum are not exists");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		// Create tree object
		var tree: BinaryTree = new BinaryTree();
		/* 
				     3
				    /  \
				   /    \
				  2      1
				   \    /  \
				    1  5    6
				   / \
				  8   7
				-----------------------
				Binary Tree
				*/
		tree.root = new Node(3);
		tree.root.left = new Node(2);
		tree.root.left.right = new Node(1);
		tree.root.right = new Node(1);
		tree.root.right.right = new Node(6);
		tree.root.right.left = new Node(5);
		tree.root.left.right.left = new Node(8);
		tree.root.left.right.right = new Node(7);
		print("\n Tree Node : \n");
		tree.print_preorder(tree.root);
		//  Test Cases
		tree.check_sum_path(9);
		tree.check_sum_path(13);
		tree.check_sum_path(15);
	}
}

Output

 Tree Node :
   3   2   1   8   7   1   5   6
 Path from root to leaf of [9] sum exists
 Path from root to leaf of [13] sum exists
 Path from root to leaf of [15] sum are not exists
/*
    Swift 4 Program 
    Root to leaf path sum equal to a given number
*/

//  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;
	}
}
// Define Binary Tree
class BinaryTree
{
	var root: Node? ;
	init()
	{
		// Set root of tree
		self.root = nil;
	}
	// Display pre order elements
	func print_preorder(_ node: Node? )
	{
		if (node != nil)
		{
			// Print node value
			print("   ", node!.data, terminator: "");
			self.print_preorder(node!.left);
			self.print_preorder(node!.right);
		}
	}
	//  Check whether the path of leaf nodes from the root is equal to the given sum?
	func find_path_sum(_ node: Node? , _ sum : Int, _ k: Int)->Bool
	{
		if (node == nil)
		{
			return false;
		}
		if (node!.left == nil && node!.right == nil && k + node!.data == sum)
		{
			//  When current node is leaf node and path is equal to given sum
			return true;
		}
		//  Recursively executing left and right subtree
		if (self.find_path_sum(node!.left, sum, node!.data + k) 
            || self.find_path_sum(node!.right, sum, node!.data + k))
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	//  Handles the request to find the sum exist in path from root to leaf nodes
	func check_sum_path(_ sum: Int)
	{
		if (self.root == nil)
		{
			print("\n Empty Tree \n", terminator: "");
			return;
		}
		if (self.find_path_sum(self.root, sum, 0))
		{
			print("\n Path from root to leaf of [", sum ,"] sum exists", terminator: "");
		}
		else
		{
			print("\n Path from root to leaf of [", sum ,"] sum are not exists", terminator: "");
		}
	}
}
func main()
{
	// Create tree object
	let tree: BinaryTree = BinaryTree();
	/* 
		     3
		    /  \
		   /    \
		  2      1
		   \    /  \
		    1  5    6
		   / \
		  8   7
		-----------------------
		Binary Tree
		*/
	tree.root = Node(3);
	tree.root!.left = Node(2);
	tree.root!.left!.right = Node(1);
	tree.root!.right = Node(1);
	tree.root!.right!.right = Node(6);
	tree.root!.right!.left = Node(5);
	tree.root!.left!.right!.left = Node(8);
	tree.root!.left!.right!.right = Node(7);
	print("\n Tree Node : \n", terminator: "");
	tree.print_preorder(tree.root);
	//  Test Cases
	tree.check_sum_path(9);
	tree.check_sum_path(13);
	tree.check_sum_path(15);
}
main();

Output

 Tree Node :
    3    2    1    8    7    1    5    6
 Path from root to leaf of [ 9 ] sum exists
 Path from root to leaf of [ 13 ] sum exists
 Path from root to leaf of [ 15 ] sum are not exists




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