Posted on by Kalkicode
Code Recursion

# Check if a pair of leaf node sum exists in given binary tree

The problem aims to determine if there exists a pair of leaf nodes in a given binary tree such that their sum matches a given target value. It involves traversing the tree and finding unique leaf nodes, then checking if a pair of such leaf nodes satisfies the sum condition.

## Problem Statement

Given a binary tree and a target sum value `k`, the task is to check whether there exists a pair of distinct leaf nodes in the tree whose values sum up to `k`. If such a pair exists, the program should output the nodes forming the pair; otherwise, it should indicate that no such pair exists.

## Example

Consider the binary tree depicted in the code:

``````
4
/   \
9     7
/ \     \
-2   5     12
/ \    / \
6   8  5   7
/   /    \
9   3     15
/ \      \
1   10     2``````

For this tree, the program should return the following results for different target sums:

1. For `k = 8`: A pair exists: (-2 + 10)
2. For `k = 2`: No such pair exists.
3. For `k = 4`: No such pair exists.
4. For `k = -1`: A pair exists: (-2 + 1)
5. For `k = 9`: A pair exists: (2 + 7)

## Idea to Solve

The problem can be approached using a hash map to store the occurrences of leaf node values. The idea is to traverse the binary tree and record the leaf node values in the hash map along with their frequency. For each leaf node value encountered, we check if the remaining value (`k - leafValue`) exists in the hash map, and we also make sure the values are distinct. If the conditions are met, a valid pair exists.

## Pseudocode

``````function findLeafNodes(node, record):
if node is null:
return
if node is leaf node:
if node.data exists in record:
increment the frequency of node.data
else:
add node.data to record with frequency 1
else:
findLeafNodes(node.left, record)
findLeafNodes(node.right, record)

function leafPairSum(k):
if root is null:
return
create empty record (hash map)
call findLeafNodes(root, record)
if size of record > 1:
for key in record:
if record contains (k - key) and (key != (k - key) or frequency > 1):
print pair (key, k - key)
return
print "No leaf pair of given sum", k
else:
print "Single leaf node exists"

main:
create binary tree
construct tree as shown
call leafPairSum for different values of k``````

## Algorithm Explanation

1. The `findLeafNodes` function recursively traverses the binary tree and records the leaf node values along with their frequencies in the hash map.
2. The `leafPairSum` function initializes an empty hash map, calls `findLeafNodes` to populate the hash map, and then checks for valid pairs using the conditions mentioned.
3. In the `main` function, a binary tree is constructed, and `leafPairSum` is called for different values of `k`.

## Program Solution

``````import java.util.HashMap;
/*
Java Program
Check if a pair of leaf node sum exists in given 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 tree root to null
this.root = null;
}
// Find all leaf nodes using recursion
public void findLeafNodes(TreeNode node,
HashMap <Integer,Integer> record)
{
if (node == null)
{
return;
}
if (node.left == null && node.right == null)
{

if (record.containsKey(node.data))
{
// Increment the element frequency
record.put(node.data,record.get(node.data)+1);
}
else
{
// Add new leaf node
record.put(node.data,1);
}

}
else
{
findLeafNodes(node.left, record);
findLeafNodes(node.right, record);
}
}
// Handles the request of check pair of leaf node sum
public void leafPairSum(int k)
{
if (this.root == null)
{
// Empty Tree
return;
}
else
{
// This is use to collect leaf nodes
HashMap < Integer, Integer > record =
new HashMap < Integer, Integer > ();
// Find all leaf nodes
findLeafNodes(this.root, record);
if (record.size() > 1)
{
System.out.print("\n Given sum k : " + k);
for (int key: record.keySet())
{
// Check that pair exist in tree
if (record.containsKey(k - key) &&
( (key != k-key) || record.get(k-key) > 1 ))
{
// Remaining amount exists in record and they are unique
// Display a pair of given sum
System.out.print("\n (" + key + " + " + (k - key) + ")");
return;
}
}
System.out.print("\n No leaf pair of given sum " + k);
}
else
{
System.out.print("\nSingle leaf node exists\n");
}
}
}
public static void main(String[] args)
{
// Create new binary tree
BinaryTree tree = new BinaryTree();
/*
4
/   \
9     7
/ \     \
-2   5     12
/ \    / \
6   8  5   7
/   /    \
9   3     15
/ \      \
1   10     2
-----------------
Constructing binary tree
*/
tree.root = new TreeNode(4);
tree.root.left = new TreeNode(9);
tree.root.left.right = new TreeNode(5);
tree.root.left.right.left = new TreeNode(6);
tree.root.left.right.left.left = new TreeNode(9);
tree.root.left.right.right = new TreeNode(8);
tree.root.left.right.right.left = new TreeNode(3);
tree.root.left.right.right.left.left = new TreeNode(1);
tree.root.left.right.right.left.right = new TreeNode(10);
tree.root.left.left = new TreeNode(-2);
tree.root.right = new TreeNode(7);
tree.root.right.right = new TreeNode(12);
tree.root.right.right.right = new TreeNode(7);
tree.root.right.right.left = new TreeNode(5);
tree.root.right.right.left.right = new TreeNode(15);
tree.root.right.right.left.right.right = new TreeNode(2);
// Test cases
tree.leafPairSum(8);
tree.leafPairSum(2);
tree.leafPairSum(4);
tree.leafPairSum(-1);
tree.leafPairSum(9);
}
}``````

#### input

`````` Given sum k : 8
(-2 + 10)
Given sum k : 2
No leaf pair of given sum 2
Given sum k : 4
No leaf pair of given sum 4
Given sum k : -1
(-2 + 1)
Given sum k : 9
(2 + 7)``````
``````// Include header file
#include <iostream>
#include <unordered_map>
using namespace std;
/*
C++ Program
Check if a pair of leaf node sum exists in given 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;
}
// Find all leaf nodes using recursion
void findLeafNodes(TreeNode *node, unordered_map < int, int > &record)
{
if (node == NULL)
{
return;
}
if (node->left == NULL && node->right == NULL)
{
if (record.find(node->data) != record.end())
{
// Increment the element frequency
record[node->data] = record[node->data] + 1;
}
else
{
// Add new leaf node
record[node->data] = 1;
}
}
else
{
this->findLeafNodes(node->left, record);
this->findLeafNodes(node->right, record);
}
}
// Handles the request of check pair of leaf node sum
void leafPairSum(int k)
{
if (this->root == NULL)
{
// Empty Tree
return;
}
else
{
// This is use to collect leaf nodes
unordered_map < int, int > record;
// Find all leaf nodes
this->findLeafNodes(this->root, record);
if ( record.size() > 1)
{
cout << "\n Given sum k : " << k;
for (auto &info: record)
{
// Check that pair exist in tree
if (record.find(k - info.first) != record.end()
&& ((info.first != k - info.first)
|| record[k - info.first] > 1))
{
// Remaining amount exists in record and they are unique
// Display a pair of given sum
cout << "\n (" << info.first << " + "
<< (k - info.first) << ")";
return;
}
}
cout << "\n No leaf pair of given sum " << k;
}
else
{
cout << "\nSingle leaf node exists\n";
}
}
}
};
int main()
{
// Create new binary tree
BinaryTree *tree = new BinaryTree();
/*
4
/   \
9     7
/ \     \
-2   5     12
/ \    / \
6   8  5   7
/   /    \
9   3     15
/ \      \
1   10     2
-----------------
Constructing binary tree
*/
tree->root = new TreeNode(4);
tree->root->left = new TreeNode(9);
tree->root->left->right = new TreeNode(5);
tree->root->left->right->left = new TreeNode(6);
tree->root->left->right->left->left = new TreeNode(9);
tree->root->left->right->right = new TreeNode(8);
tree->root->left->right->right->left = new TreeNode(3);
tree->root->left->right->right->left->left = new TreeNode(1);
tree->root->left->right->right->left->right = new TreeNode(10);
tree->root->left->left = new TreeNode(-2);
tree->root->right = new TreeNode(7);
tree->root->right->right = new TreeNode(12);
tree->root->right->right->right = new TreeNode(7);
tree->root->right->right->left = new TreeNode(5);
tree->root->right->right->left->right = new TreeNode(15);
tree->root->right->right->left->right->right = new TreeNode(2);
// Test cases
tree->leafPairSum(8);
tree->leafPairSum(2);
tree->leafPairSum(4);
tree->leafPairSum(-1);
tree->leafPairSum(9);
return 0;
}``````

#### input

`````` Given sum k : 8
(7 + 1)
Given sum k : 2
No leaf pair of given sum 2
Given sum k : 4
No leaf pair of given sum 4
Given sum k : -1
(-2 + 1)
Given sum k : 9
(7 + 2)``````
``````// Include namespace system
using System;
using System.Collections.Generic;
/*
Csharp Program
Check if a pair of leaf node sum exists in given 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 tree root to null
this.root = null;
}
// Find all leaf nodes using recursion
public void findLeafNodes(TreeNode node, Dictionary < int, int > record)
{
if (node == null)
{
return;
}
if (node.left == null && node.right == null)
{
if (record.ContainsKey(node.data))
{
// Increment the element frequency
record[node.data] = record[node.data] + 1;
}
else
{
// Add new leaf node
}
}
else
{
this.findLeafNodes(node.left, record);
this.findLeafNodes(node.right, record);
}
}
// Handles the request of check pair of leaf node sum
public void leafPairSum(int k)
{
if (this.root == null)
{
// Empty Tree
return;
}
else
{
// This is use to collect leaf nodes
Dictionary < int, int > record = new Dictionary < int, int > ();
// Find all leaf nodes
this.findLeafNodes(this.root, record);
if (record.Count > 1)
{
Console.Write("\n Given sum k : " + k);
foreach(KeyValuePair < int, int > info in record)
{
// Check that pair exist in tree
if (record.ContainsKey(k - info.Key)
&& ((info.Key != k - info.Key) || info.Value > 1))
{
// Remaining amount exists in record and they are unique
// Display a pair of given sum
Console.Write("\n (" + info.Key + " + " + (k - info.Key) + ")");
return;
}
}
Console.Write("\n No leaf pair of given sum " + k);
}
else
{
Console.Write("\nSingle leaf node exists\n");
}
}
}
public static void Main(String[] args)
{
// Create new binary tree
BinaryTree tree = new BinaryTree();
/*
4
/   \
9     7
/ \     \
-2   5     12
/ \    / \
6   8  5   7
/   /    \
9   3     15
/ \      \
1   10     2
-----------------
Constructing binary tree
*/
tree.root = new TreeNode(4);
tree.root.left = new TreeNode(9);
tree.root.left.right = new TreeNode(5);
tree.root.left.right.left = new TreeNode(6);
tree.root.left.right.left.left = new TreeNode(9);
tree.root.left.right.right = new TreeNode(8);
tree.root.left.right.right.left = new TreeNode(3);
tree.root.left.right.right.left.left = new TreeNode(1);
tree.root.left.right.right.left.right = new TreeNode(10);
tree.root.left.left = new TreeNode(-2);
tree.root.right = new TreeNode(7);
tree.root.right.right = new TreeNode(12);
tree.root.right.right.right = new TreeNode(7);
tree.root.right.right.left = new TreeNode(5);
tree.root.right.right.left.right = new TreeNode(15);
tree.root.right.right.left.right.right = new TreeNode(2);
// Test cases
tree.leafPairSum(8);
tree.leafPairSum(2);
tree.leafPairSum(4);
tree.leafPairSum(-1);
tree.leafPairSum(9);
}
}``````

#### input

`````` Given sum k : 8
(-2 + 10)
Given sum k : 2
No leaf pair of given sum 2
Given sum k : 4
No leaf pair of given sum 4
Given sum k : -1
(-2 + 1)
Given sum k : 9
(2 + 7)``````
``````<?php
/*
Php Program
Check if a pair of leaf node sum exists in given 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;
}
// Find all leaf nodes using recursion
public	function findLeafNodes(\$node, &\$record)
{
if (\$node == NULL)
{
return;
}
if (\$node->left == NULL && \$node->right == NULL)
{
if (array_key_exists(\$node->data, \$record))
{
// Increment the element frequency
\$record[\$node->data] = \$record[\$node->data] + 1;
}
else
{
// Add new leaf node
\$record[\$node->data] = 1;
}
}
else
{
\$this->findLeafNodes(\$node->left, \$record);
\$this->findLeafNodes(\$node->right, \$record);
}
}
// Handles the request of check pair of leaf node sum
public	function leafPairSum(\$k)
{
if (\$this->root == NULL)
{
// Empty Tree
return;
}
else
{
// This is use to collect leaf nodes
\$record = array();
// Find all leaf nodes
\$this->findLeafNodes(\$this->root, \$record);
if (count(\$record) > 1)
{
echo("\n Given sum k : ".\$k);
foreach(\$record as \$key => \$value)
{
// Check that pair exist in tree
if (array_key_exists(\$k - \$key, \$record)
&& ((\$key != \$k - \$key) || \$value > 1))
{
// Remaining amount exists in record and they are unique
// Display a pair of given sum
echo ("\n (".\$key." + ".(\$k - \$key).")");
return;
}
}
echo("\n No leaf pair of given sum ".\$k);
}
else
{
echo("\nSingle leaf node exists\n");
}
}
}
}

function main()
{
// Create new binary tree
\$tree = new BinaryTree();
/*
4
/   \
9     7
/ \     \
-2   5     12
/ \    / \
6   8  5   7
/   /    \
9   3     15
/ \      \
1   10     2
-----------------
Constructing binary tree
*/
\$tree->root = new TreeNode(4);
\$tree->root->left = new TreeNode(9);
\$tree->root->left->right = new TreeNode(5);
\$tree->root->left->right->left = new TreeNode(6);
\$tree->root->left->right->left->left = new TreeNode(9);
\$tree->root->left->right->right = new TreeNode(8);
\$tree->root->left->right->right->left = new TreeNode(3);
\$tree->root->left->right->right->left->left = new TreeNode(1);
\$tree->root->left->right->right->left->right = new TreeNode(10);
\$tree->root->left->left = new TreeNode(-2);
\$tree->root->right = new TreeNode(7);
\$tree->root->right->right = new TreeNode(12);
\$tree->root->right->right->right = new TreeNode(7);
\$tree->root->right->right->left = new TreeNode(5);
\$tree->root->right->right->left->right = new TreeNode(15);
\$tree->root->right->right->left->right->right = new TreeNode(2);
// Test cases
\$tree->leafPairSum(8);
\$tree->leafPairSum(2);
\$tree->leafPairSum(4);
\$tree->leafPairSum(-1);
\$tree->leafPairSum(9);
}
main();``````

#### input

`````` Given sum k : 8
(-2 + 10)
Given sum k : 2
No leaf pair of given sum 2
Given sum k : 4
No leaf pair of given sum 4
Given sum k : -1
(-2 + 1)
Given sum k : 9
(2 + 7)``````
``````/*
Node JS Program
Check if a pair of leaf node sum exists in given 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;
}
// Find all leaf nodes using recursion
findLeafNodes(node, record)
{
if (node == null)
{
return;
}
if (node.left == null && node.right == null)
{
if (record.has(node.data))
{
// Increment the element frequency
record.set(node.data, record.get(node.data) + 1);
}
else
{
// Add new leaf node
record.set(node.data, 1);
}
}
else
{
this.findLeafNodes(node.left, record);
this.findLeafNodes(node.right, record);
}
}
// Handles the request of check pair of leaf node sum
leafPairSum(k)
{
if (this.root == null)
{
// Empty Tree
return;
}
else
{
// This is use to collect leaf nodes
var record = new Map();
// Find all leaf nodes
this.findLeafNodes(this.root, record);
if (record.size > 1)
{
process.stdout.write("\n Given sum k : " + k);
for (let [key, value] of record)
{
// Check that pair exist in tree
if (record.has(k - key)
&& ((key != k - key) || value > 1))
{
// Remaining amount exists in record and they are unique
// Display a pair of given sum
process.stdout.write("\n (" + key + " + " + (k - key) + ")");
return;
}
}
process.stdout.write("\n No leaf pair of given sum " + k);
}
else
{
process.stdout.write("\n Single leaf node exists\n");
}
}
}
}

function main()
{
// Create new binary tree
var tree = new BinaryTree();
/*
4
/   \
9     7
/ \     \
-2   5     12
/ \    / \
6   8  5   7
/   /    \
9   3     15
/ \      \
1   10     2
-----------------
Constructing binary tree
*/
tree.root = new TreeNode(4);
tree.root.left = new TreeNode(9);
tree.root.left.right = new TreeNode(5);
tree.root.left.right.left = new TreeNode(6);
tree.root.left.right.left.left = new TreeNode(9);
tree.root.left.right.right = new TreeNode(8);
tree.root.left.right.right.left = new TreeNode(3);
tree.root.left.right.right.left.left = new TreeNode(1);
tree.root.left.right.right.left.right = new TreeNode(10);
tree.root.left.left = new TreeNode(-2);
tree.root.right = new TreeNode(7);
tree.root.right.right = new TreeNode(12);
tree.root.right.right.right = new TreeNode(7);
tree.root.right.right.left = new TreeNode(5);
tree.root.right.right.left.right = new TreeNode(15);
tree.root.right.right.left.right.right = new TreeNode(2);
// Test cases
tree.leafPairSum(8);
tree.leafPairSum(2);
tree.leafPairSum(4);
tree.leafPairSum(-1);
tree.leafPairSum(9);
}
main();``````

#### input

`````` Given sum k : 8
(-2 + 10)
Given sum k : 2
No leaf pair of given sum 2
Given sum k : 4
No leaf pair of given sum 4
Given sum k : -1
(-2 + 1)
Given sum k : 9
(2 + 7)``````
``````#    Python 3 Program
#    Check if a pair of leaf node sum exists in given 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

#  Find all leaf nodes using recursion
def findLeafNodes(self, node, record) :
if (node == None) :
return

if (node.left == None and node.right == None) :
if (node.data in record.keys()) :
#  Increment the element frequency
record[node.data] = record[node.data] + 1
else :
#  Add new leaf node
record[node.data] = 1

else :
self.findLeafNodes(node.left, record)
self.findLeafNodes(node.right, record)

#  Handles the request of check pair of leaf node sum
def leafPairSum(self, k) :
if (self.root == None) :
#  Empty Tree
return
else :
#  This is use to collect leaf nodes
record = dict()
#  Find all leaf nodes
self.findLeafNodes(self.root, record)
if (len(record) > 1) :
print("\n Given sum k : ", k, end = "")
for key, value in record.items() :
#  Check that pair exist in tree
if (k - key in record.keys() and
((key != k - key) or value > 1)) :
#  Remaining amount exists in record and they are unique
#  Display a pair of given sum
print("\n (", key ,",", (k - key) ,")", end = "")
return

print("\n No leaf pair of given sum ", k, end = "")
else :
print("\nSingle leaf node exists")

def main() :
#  Create new binary tree
tree = BinaryTree()
#         4
#       /   \
#      9     7
#     / \     \
#   -2   5     12
#       / \    / \
#      6   8  5   7
#     /   /    \
#    9   3     15
#       / \      \
#      1   10     2
# -----------------
# Constructing binary tree
tree.root = TreeNode(4)
tree.root.left = TreeNode(9)
tree.root.left.right = TreeNode(5)
tree.root.left.right.left = TreeNode(6)
tree.root.left.right.left.left = TreeNode(9)
tree.root.left.right.right = TreeNode(8)
tree.root.left.right.right.left = TreeNode(3)
tree.root.left.right.right.left.left = TreeNode(1)
tree.root.left.right.right.left.right = TreeNode(10)
tree.root.left.left = TreeNode(-2)
tree.root.right = TreeNode(7)
tree.root.right.right = TreeNode(12)
tree.root.right.right.right = TreeNode(7)
tree.root.right.right.left = TreeNode(5)
tree.root.right.right.left.right = TreeNode(15)
tree.root.right.right.left.right.right = TreeNode(2)
#  Test cases
tree.leafPairSum(8)
tree.leafPairSum(2)
tree.leafPairSum(4)
tree.leafPairSum(-1)
tree.leafPairSum(9)

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

#### input

`````` Given sum k :  8
( 1 , 7 )
Given sum k :  2
No leaf pair of given sum  2
Given sum k :  4
No leaf pair of given sum  4
Given sum k :  -1
( 1 , -2 )
Given sum k :  9
( 2 , 7 )``````
``````#    Ruby Program
#    Check if a pair of leaf node sum exists in given 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_accessor :root
def initialize()
self.root = nil
end

#  Find all leaf nodes using recursion
def findLeafNodes(node, record)
if (node == nil)
return
end

if (node.left == nil && node.right == nil)
if (record.key?(node.data))
#  Increment the element frequency
record[node.data] = record[node.data] + 1
else
#  Add new leaf node
record[node.data] = 1
end

else
self.findLeafNodes(node.left, record)
self.findLeafNodes(node.right, record)
end

end

#  Handles the request of check pair of leaf node sum
def leafPairSum(k)
if (self.root == nil)
#  Empty Tree
return
else
#  This is use to collect leaf nodes
record = Hash.new()
#  Find all leaf nodes
self.findLeafNodes(self.root, record)
if (record.size() > 1)
print("\n Given sum k : ", k)
record.each { | key, value |
#  Check that pair exist in tree
if (record.key?(k - key) &&
((key != k - key) || value > 1))
#  Remaining amount exists in record and they are unique
#  Display a pair of given sum
print("\n (", key ,", ", (k - key) ,")")
return
end

}
print("\n No leaf pair of given sum ", k)
else
print("\nSingle leaf node exists\n")
end

end

end

end

def main()
#  Create new binary tree
tree = BinaryTree.new()
#         4
#       /   \
#      9     7
#     / \     \
#   -2   5     12
#       / \    / \
#      6   8  5   7
#     /   /    \
#    9   3     15
#       / \      \
#      1   10     2
# -----------------
# Constructing binary tree
tree.root = TreeNode.new(4)
tree.root.left = TreeNode.new(9)
tree.root.left.right = TreeNode.new(5)
tree.root.left.right.left = TreeNode.new(6)
tree.root.left.right.left.left = TreeNode.new(9)
tree.root.left.right.right = TreeNode.new(8)
tree.root.left.right.right.left = TreeNode.new(3)
tree.root.left.right.right.left.left = TreeNode.new(1)
tree.root.left.right.right.left.right = TreeNode.new(10)
tree.root.left.left = TreeNode.new(-2)
tree.root.right = TreeNode.new(7)
tree.root.right.right = TreeNode.new(12)
tree.root.right.right.right = TreeNode.new(7)
tree.root.right.right.left = TreeNode.new(5)
tree.root.right.right.left.right = TreeNode.new(15)
tree.root.right.right.left.right.right = TreeNode.new(2)
#  Test cases
tree.leafPairSum(8)
tree.leafPairSum(2)
tree.leafPairSum(4)
tree.leafPairSum(-1)
tree.leafPairSum(9)
end

main()``````

#### input

`````` Given sum k : 8
(-2, 10)
Given sum k : 2
No leaf pair of given sum 2
Given sum k : 4
No leaf pair of given sum 4
Given sum k : -1
(-2, 1)
Given sum k : 9
(2, 7)``````
``````import scala.collection.mutable._;
/*
Scala Program
Check if a pair of leaf node sum exists in given 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);
}
// Find all leaf nodes using recursion
def findLeafNodes(node: TreeNode, record: HashMap[Int, Int]): Unit = {
if (node == null)
{
return;
}
if (node.left == null && node.right == null)
{
if (record.contains(node.data))
{
// Increment the element frequency
record.addOne(node.data, record.get(node.data).get + 1);
}
else
{
// Add new leaf node
}
}
else
{
findLeafNodes(node.left, record);
findLeafNodes(node.right, record);
}
}
// Handles the request of check pair of leaf node sum
def leafPairSum(k: Int): Unit = {
if (this.root == null)
{
// Empty Tree
return;
}
else
{
// This is use to collect leaf nodes
var record: HashMap[Int, Int] = new HashMap[Int, Int]();
// Find all leaf nodes
findLeafNodes(this.root, record);
if (record.size > 1)
{
print("\n Given sum k : " + k);
for((key, value) <- record)
{
// Check that pair exist in tree
if (record.contains(k - key) &&
((key != k - key) || value > 1))
{
// Remaining amount exists in record and they are unique
// Display a pair of given sum
print("\n (" + key + " + " + (k - key) + ")");
return;
}
}
print("\n No leaf pair of given sum " + k);
}
else
{
print("\nSingle leaf node exists\n");
}
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
// Create new binary tree
var tree: BinaryTree = new BinaryTree();
/*
4
/   \
9     7
/ \     \
-2   5     12
/ \    / \
6   8  5   7
/   /    \
9   3     15
/ \      \
1   10     2
-----------------
Constructing binary tree
*/
tree.root = new TreeNode(4);
tree.root.left = new TreeNode(9);
tree.root.left.right = new TreeNode(5);
tree.root.left.right.left = new TreeNode(6);
tree.root.left.right.left.left = new TreeNode(9);
tree.root.left.right.right = new TreeNode(8);
tree.root.left.right.right.left = new TreeNode(3);
tree.root.left.right.right.left.left = new TreeNode(1);
tree.root.left.right.right.left.right = new TreeNode(10);
tree.root.left.left = new TreeNode(-2);
tree.root.right = new TreeNode(7);
tree.root.right.right = new TreeNode(12);
tree.root.right.right.right = new TreeNode(7);
tree.root.right.right.left = new TreeNode(5);
tree.root.right.right.left.right = new TreeNode(15);
tree.root.right.right.left.right.right = new TreeNode(2);
// Test cases
tree.leafPairSum(8);
tree.leafPairSum(2);
tree.leafPairSum(4);
tree.leafPairSum(-1);
tree.leafPairSum(9);
}
}``````

#### input

`````` Given sum k : 8
(-2 + 10)
Given sum k : 2
No leaf pair of given sum 2
Given sum k : 4
No leaf pair of given sum 4
Given sum k : -1
(-2 + 1)
Given sum k : 9
(2 + 7)``````
``````import Foundation;
/*
Swift 4 Program
Check if a pair of leaf node sum exists in given 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;
}
// Find all leaf nodes using recursion
func findLeafNodes(_ node: TreeNode? , _ record : inout[Int : Int])
{
if (node == nil)
{
return;
}
if (node!.left == nil && node!.right == nil)
{
if (record.keys.contains(node!.data))
{
// Increment the element frequency
record[node!.data] = record[node!.data]! + 1;
}
else
{
// Add new leaf node
record[node!.data] = 1;
}
}
else
{
self.findLeafNodes(node!.left, &record);
self.findLeafNodes(node!.right, &record);
}
}
// Handles the request of check pair of leaf node sum
func leafPairSum(_ k: Int)
{
if (self.root == nil)
{
// Empty Tree
return;
}
else
{
// This is use to collect leaf nodes
var record = [Int : Int]();
// Find all leaf nodes
self.findLeafNodes(self.root, &record);
if (record.count > 1)
{
print("\n Given sum k : ", k, terminator: "");
for (key, value) in record
{
// Check that pair exist in tree
if (record.keys.contains(k - key)
&& ((key  != k - key) || value > 1))
{
// Remaining amount exists in record and they are unique
// Display a pair of given sum
print("\n (", key ,"+", (k - key) ,")", terminator: "");
return;
}
}
print("\n No leaf pair of given sum ", k, terminator: "");
}
else
{
print("\nSingle leaf node exists");
}
}
}
}
func main()
{
// Create new binary tree
let tree = BinaryTree();
/*
4
/   \
9     7
/ \     \
-2   5     12
/ \    / \
6   8  5   7
/   /    \
9   3     15
/ \      \
1   10     2
-----------------
Constructing binary tree
*/
tree.root = TreeNode(4);
tree.root!.left = TreeNode(9);
tree.root!.left!.right = TreeNode(5);
tree.root!.left!.right!.left = TreeNode(6);
tree.root!.left!.right!.left!.left = TreeNode(9);
tree.root!.left!.right!.right = TreeNode(8);
tree.root!.left!.right!.right!.left = TreeNode(3);
tree.root!.left!.right!.right!.left!.left = TreeNode(1);
tree.root!.left!.right!.right!.left!.right = TreeNode(10);
tree.root!.left!.left = TreeNode(-2);
tree.root!.right = TreeNode(7);
tree.root!.right!.right = TreeNode(12);
tree.root!.right!.right!.right = TreeNode(7);
tree.root!.right!.right!.left = TreeNode(5);
tree.root!.right!.right!.left!.right = TreeNode(15);
tree.root!.right!.right!.left!.right!.right = TreeNode(2);
// Test cases
tree.leafPairSum(8);
tree.leafPairSum(2);
tree.leafPairSum(4);
tree.leafPairSum(-1);
tree.leafPairSum(9);
}
main();``````

#### input

`````` Given sum k :  8
( -2 + 10 )
Given sum k :  2
No leaf pair of given sum  2
Given sum k :  4
No leaf pair of given sum  4
Given sum k :  -1
( -2 + 1 )
Given sum k :  9
( 7 + 2 )``````
``````/*
Kotlin Program
Check if a pair of leaf node sum exists in given 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;
}
// Find all leaf nodes using recursion
fun findLeafNodes(node: TreeNode ? , record : MutableMap<Int, Int>  ): Unit
{
if (node == null)
{
return;
}
if (node.left == null && node.right == null)
{
if (record.containsKey(node.data))
{
// Increment the element frequency
record.put(node.data, record.getValue(node.data) + 1);
}
else
{
// Add new leaf node
record.put(node.data, 1);
}
}
else
{
this.findLeafNodes(node.left, record);
this.findLeafNodes(node.right, record);
}
}
// Handles the request of check pair of leaf node sum
fun leafPairSum(k: Int): Unit
{
if (this.root == null)
{
// Empty Tree
return;
}
else
{
// This is use to collect leaf nodes
var record = mutableMapOf < Int , Int > ();
// Find all leaf nodes
this.findLeafNodes(this.root, record);
if (record.count() > 1)
{
print("\n Given sum k : " + k);
for ((key, value) in record)
{
// Check that pair exist in tree
if (record.containsKey(k - key)
&& ((key != k - key) || value > 1))
{
// Remaining amount exists in record and they are unique
// Display a pair of given sum
print("\n (" + key + " + " + (k - key) + ")");
return;
}
}
print("\n No leaf pair of given sum " + k);
}
else
{
print("\nSingle leaf node exists\n");
}
}
}
}
fun main(args: Array < String > ): Unit
{
// Create new binary tree
val tree: BinaryTree = BinaryTree();
/*
4
/   \
9     7
/ \     \
-2   5     12
/ \    / \
6   8  5   7
/   /    \
9   3     15
/ \      \
1   10     2
-----------------
Constructing binary tree
*/
tree.root = TreeNode(4);
tree.root?.left = TreeNode(9);
tree.root?.left?.right = TreeNode(5);
tree.root?.left?.right?.left = TreeNode(6);
tree.root?.left?.right?.left?.left = TreeNode(9);
tree.root?.left?.right?.right = TreeNode(8);
tree.root?.left?.right?.right?.left = TreeNode(3);
tree.root?.left?.right?.right?.left?.left = TreeNode(1);
tree.root?.left?.right?.right?.left?.right = TreeNode(10);
tree.root?.left?.left = TreeNode(-2);
tree.root?.right = TreeNode(7);
tree.root?.right?.right = TreeNode(12);
tree.root?.right?.right?.right = TreeNode(7);
tree.root?.right?.right?.left = TreeNode(5);
tree.root?.right?.right?.left?.right = TreeNode(15);
tree.root?.right?.right?.left?.right?.right = TreeNode(2);
// Test cases
tree.leafPairSum(8);
tree.leafPairSum(2);
tree.leafPairSum(4);
tree.leafPairSum(-1);
tree.leafPairSum(9);
}``````

#### input

`````` Given sum k : 8
(-2 + 10)
Given sum k : 2
No leaf pair of given sum 2
Given sum k : 4
No leaf pair of given sum 4
Given sum k : -1
(-2 + 1)
Given sum k : 9
(2 + 7)``````

## Time Complexity

The time complexity of the solution depends on the number of leaf nodes and the hash map operations. In the worst case, we traverse all leaf nodes and perform hash map operations on each of them. Thus, 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.

Categories
Relative Post