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
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