Given a Binary Tree and an integer K, the task is to check if the Tree consists of a pair of leaf nodes with sum exactly K. In case of multiple pairs, print any one of them. Otherwise print -1.
Note: Assume that the given binary tree will always have more than 1 leaf node.
Examples:
Input: X = 13
1 / \ 2 3 / \ / \ 4 5 6 7 \ 8Output: [5, 8]
Explanation:
The given binary tree consists of 4 leaf nodes [4, 5, 6, 8].
The pair of nodes valued 5 and 8 have sum 13.Input: X = 6
-1 / \ 2 3 / \ 4 5Output: [-1]
Explanation:
The given binary tree consists of 3 leaf nodes [4, 5, 3].
No valid pair of nodes exists whose sum of their values equal to 6.
Therefore, print -1.
Naive Approach: The simplest approach to solve the problem is to traverse the tree and store all the leaf nodes in an array. Then sort the array and use two pointer technique to find if a required pair exists or not.
Time Complexity: O(NlogN)
Auxiliary Space: O(N)
Efficient Approach: The above approach can be optimized using HashSet. Follow the steps below to solve the problem:
- Create a Set to store values of leaf nodes.
- Traverse the tree and for every leaf node, check if (K – value of leaf node) exists in the unordered set or not.
- If found to be true, print the pair of node values.
- Otherwise store the value of the current node into the unordered set.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Stores if a pair exists or notbool pairFound = false;// Struct binary tree nodestruct Node { int data; Node *left, *right;};// Creates a new nodeNode* newNode(int data){ Node* temp = new Node(); temp->data = data; temp->left = temp->right = NULL; return temp;}// Function to check if a pair of leaf// nodes exists with sum Kvoid pairSum(Node* root, int target, unordered_set<int>& S){ // checks if root is NULL if (!root) return; // Checks if the current node is a leaf node if (!root->left and !root->right) { // Checks for a valid pair of leaf nodes if (S.count(target - root->data)) { cout << target - root->data << " " << root->data; pairFound = true; return; } // Insert value of current node // into the set else S.insert(root->data); } // Traverse left and right subtree pairSum(root->left, target, S); pairSum(root->right, target, S);}// Driver Codeint main(){ // Construct binary tree Node* root = newNode(1); root->left = newNode(2); root->left->left = newNode(4); root->left->right = newNode(5); root->right = newNode(3); root->right->left = newNode(6); root->right->right = newNode(7); root->right->right->right = newNode(8); // Stores the leaf nodes unordered_set<int> S; int K = 13; pairSum(root, K, S); if (pairFound == false) cout << "-1"; return 0;} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{// Stores if a pair exists or notstatic boolean pairFound = false;// Struct binary tree nodestatic class Node { int data; Node left, right;};// Creates a new nodestatic Node newNode(int data){ Node temp = new Node(); temp.data = data; temp.left = temp.right = null; return temp;}// Function to check if a pair of leaf// nodes exists with sum Kstatic void pairSum(Node root, int target, HashSet<Integer> S){ // Checks if root is null if (root == null) return; // Checks if the current node is a leaf node if (root.left == null && root.right == null) { // Checks for a valid pair of leaf nodes if (S.contains(target - root.data)) { System.out.print(target - root.data + " " + root.data); pairFound = true; return; } // Insert value of current node // into the set else S.add(root.data); } // Traverse left and right subtree pairSum(root.left, target, S); pairSum(root.right, target, S);}// Driver Codepublic static void main(String[] args){ // Construct binary tree Node root = newNode(1); root.left = newNode(2); root.left.left = newNode(4); root.left.right = newNode(5); root.right = newNode(3); root.right.left = newNode(6); root.right.right = newNode(7); root.right.right.right = newNode(8); // Stores the leaf nodes HashSet<Integer> S = new HashSet<Integer>(); int K = 13; pairSum(root, K, S); if (pairFound == false) System.out.print("-1");}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program to implement# the above approach# Stores if a pair exists or notpairFound = FalseS = set()# Struct binary tree nodeclass newNode: def __init__(self, data): self.data = data self.left = None self.right = None# Function to check if a pair of # leaf nodes exists with sum Kdef pairSum(root, target): global pairFound global S # Checks if root is NULL if (root == None): return # Checks if the current node # is a leaf node if (root.left == None and root.right == None): temp = list(S) # Checks for a valid pair of leaf nodes if (temp.count(target - root.data)): print(target - root.data, root.data) pairFound = True return # Insert value of current node # into the set else: S.add(root.data) # Traverse left and right subtree pairSum(root.left, target) pairSum(root.right, target)# Driver Codeif __name__ == '__main__': # Construct binary tree root = newNode(1) root.left = newNode(2) root.left.left = newNode(4) root.left.right = newNode(5) root.right = newNode(3) root.right.left = newNode(6) root.right.right = newNode(7) root.right.right.right = newNode(8) K = 13 pairSum(root, K) if (pairFound == False): print(-1) # This code is contributed by bgangwar59 |
C#
// C# program to implement// the above approachusing System;using System.Collections.Generic;class GFG{// Stores if a pair exists or notstatic bool pairFound = false;// Struct binary tree nodeclass Node { public int data; public Node left, right;};// Creates a new nodestatic Node newNode(int data){ Node temp = new Node(); temp.data = data; temp.left = temp.right = null; return temp;}// Function to check if a pair of leaf// nodes exists with sum Kstatic void pairSum(Node root, int target, HashSet<int> S){ // Checks if root is null if (root == null) return; // Checks if the current node is a leaf node if (root.left == null && root.right == null) { // Checks for a valid pair of leaf nodes if (S.Contains(target - root.data)) { Console.Write(target - root.data + " " + root.data); pairFound = true; return; } // Insert value of current node // into the set else S.Add(root.data); } // Traverse left and right subtree pairSum(root.left, target, S); pairSum(root.right, target, S);}// Driver Codepublic static void Main(String[] args){ // Construct binary tree Node root = newNode(1); root.left = newNode(2); root.left.left = newNode(4); root.left.right = newNode(5); root.right = newNode(3); root.right.left = newNode(6); root.right.right = newNode(7); root.right.right.right = newNode(8); // Stores the leaf nodes HashSet<int> S = new HashSet<int>(); int K = 13; pairSum(root, K, S); if (pairFound == false) Console.Write("-1");}}// This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript implementation of the above approach // Stores if a pair exists or not let pairFound = false; // Struct binary tree node class Node { constructor(data) { this.left = null; this.right = null; this.data = data; } } // Creates a new node function newNode(data) { let temp = new Node(data); return temp; } // Function to check if a pair of leaf // nodes exists with sum K function pairSum(root, target, S) { // Checks if root is null if (root == null) return; // Checks if the current node is a leaf node if (root.left == null && root.right == null) { // Checks for a valid pair of leaf nodes if (S.has(target - root.data)) { document.write(target - root.data + " " + root.data); pairFound = true; return; } // Insert value of current node // into the set else S.add(root.data); } // Traverse left and right subtree pairSum(root.left, target, S); pairSum(root.right, target, S); } // Construct binary tree let root = newNode(1); root.left = newNode(2); root.left.left = newNode(4); root.left.right = newNode(5); root.right = newNode(3); root.right.left = newNode(6); root.right.right = newNode(7); root.right.right.right = newNode(8); // Stores the leaf nodes let S = new Set(); let K = 13; pairSum(root, K, S); if (pairFound == false) document.write("-1"); </script> |
Output:
5 8
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
