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

Here given code implementation process.

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
				record.Add(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 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_reader :root
	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
				record.addOne(node.data, 1);
			}
		}
		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)


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







© 2021, kalkicode.com, All rights reserved