Given a Binary Search Tree and a SUM. The task is to check if there exists any triplet(group of 3 elements) in the given BST with the given SUM.
Examples:
Input : SUM = 21 Output : YES There exists a triplet (7, 3, 11) in the above given BST with sum 21. Input : SUM = 101 Output : NO
It is known that elements in the inorder traversal of BST are sorted in increasing order. So, the idea is to do inorder traversal on the given BST and store the elements in a vector or array. Now the task reduces to check for a triplet with given sum in a sorted array.
Now to do this, start traversing the array and for every element A[i] check for a pair with a sum (SUM – A[i]) in the remaining sorted array.
To do this:
1) Initialize two index variables to find the candidate
elements in the sorted array.
(a) Initialize first to the leftmost index: l = 0
(b) Initialize second the rightmost index: r = ar_size-1
2) Loop while l < r.
(a) If (A[l] + A[r] == sum) then return 1
(b) Else if( A[l] + A[r] < sum ) then l++
(c) Else r--
3) If no such candidates are found in the whole array,
return 0
Below is the implementation of the above approach:
C++
// C++ program to check if a triplet with// given SUM exists in the BST or not#include <bits/stdc++.h>using namespace std;struct Node { int key; struct Node *left, *right;};// A utility function to create a new BST nodestruct Node* newNode(int item){ Node* temp = new Node; temp->key = item; temp->left = temp->right = NULL; return temp;}// A utility function to do inorder traversal// of the BST and store values in a vectorvoid inorder(Node* root, vector<int>& vec){ if (root != NULL) { inorder(root->left, vec); vec.push_back(root->key); inorder(root->right, vec); }}// A utility function to insert a new node// with given key in BSTstruct Node* insert(Node* node, int key){ /* If the tree is empty, return a new node */ if (node == NULL) return newNode(key); /* Otherwise, recur down the tree */ if (key < node->key) node->left = insert(node->left, key); else if (key > node->key) node->right = insert(node->right, key); /* return the (unchanged) node pointer */ return node;}// Function to check if a triplet with given SUM// exists in the BST or notbool checkForTriplet(Node* root, int sum){ // Vector to store the inorder traversal // of the BST vector<int> vec; // Call inorder() to do the inorder // on the BST and store it in vec inorder(root, vec); // Now, check if any triplet with given sum // exists in the BST or not int l, r; // Now fix the first element one by one and find the // other two elements for (int i = 0; i < vec.size() - 2; i++) { // To find the other two elements, start two index // variables from two corners of the array and move // them toward each other l = i + 1; // index of the first element in the // remaining elements // index of the last element r = vec.size() - 1; while (l < r) { if (vec[i] + vec[l] + vec[r] == sum) { return true; } else if (vec[i] + vec[l] + vec[r] < sum) l++; else // vec[i] + vec[l] + vec[r] > sum r--; } } // If we reach here, then no triplet was found return false;}// Driver Codeint main(){ /* Let us create following BST 50 / \ 30 70 / \ / \ 20 40 60 80 */ struct Node* root = NULL; root = insert(root, 50); insert(root, 30); insert(root, 20); insert(root, 40); insert(root, 70); insert(root, 60); insert(root, 80); int sum = 120; if (checkForTriplet(root, sum)) cout << "YES"; else cout << "NO"; return 0;} |
Java
// Java program to check if a triplet with// given SUM exists in the BST or notimport java.util.*;class GFG{static class Node { int key; Node left, right;};// A utility function to // create a new BST nodestatic Node newNode(int item){ Node temp = new Node(); temp.key = item; temp.left = temp.right = null; return temp;}// A utility function to do inorder traversal// of the BST and store values in a vectorstatic void inorder(Node root, Vector<Integer> vec){ if (root != null) { inorder(root.left, vec); vec.add(root.key); inorder(root.right, vec); }}// A utility function to insert a new node// with given key in BSTstatic Node insert(Node node, int key){ /* If the tree is empty, return a new node */ if (node == null) return newNode(key); /* Otherwise, recur down the tree */ if (key < node.key) node.left = insert(node.left, key); else if (key > node.key) node.right = insert(node.right, key); /* return the (unchanged) node pointer */ return node;}// Function to check if a triplet with // given SUM exists in the BST or notstatic boolean checkForTriplet(Node root, int sum){ // Vector to store the inorder traversal // of the BST Vector<Integer> vec = new Vector<Integer>(); // Call inorder() to do the inorder // on the BST and store it in vec inorder(root, vec); // Now, check if any triplet with given sum // exists in the BST or not int l, r; // Now fix the first element one by one // and find the other two elements for (int i = 0; i < vec.size() - 2; i++) { // To find the other two elements, // start two index variables from two corners // of the array and move them toward each other l = i + 1; // index of the first element in the // remaining elements // index of the last element r = vec.size() - 1; while (l < r) { if (vec.get(i) + vec.get(l) + vec.get(r) == sum) { return true; } else if (vec.get(i) + vec.get(l) + vec.get(r) < sum) l++; else // vec[i] + vec[l] + vec[r] > sum r--; } } // If we reach here, // then no triplet was found return false;}// Driver Codepublic static void main(String[] args){ /* Let us create following BST 50 / \ 30 70 / \ / \ 20 40 60 80 */ Node root = null; root = insert(root, 50); insert(root, 30); insert(root, 20); insert(root, 40); insert(root, 70); insert(root, 60); insert(root, 80); int sum = 120; if (checkForTriplet(root, sum)) System.out.print("YES"); else System.out.print("NO");}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program to check if a triplet with# given SUM exists in the BST or notclass Node: def __init__(self, data): self.data = data self.right = self.left = None# A utility function to insert a # new node with given key in BSTdef insert(root, x): if root is None: root = Node(x) else: if root.data < x: if root.right is None: root.right = Node(x) else: insert(root.right, x) else: if root.left is None: root.left = Node(x) else: insert(root.left, x)# A utility function to do inorder # traversal of the BST and store # values in an arraydef inorder(root, ior): if root is None: return inorder(root.left, ior) ior.append(root.data) inorder(root.right, ior)# Function to check if a triplet with# given SUM exists in the BST or notdef checkForTriplet(root, sum): # Initialize an empty array vec = [0] # Call to function inorder to # store values in array inorder(root, vec) # Traverse the array and find # triplet with sum for i in range(0, len(vec) - 2, 1): l = i + 1 # Index of the last element r = len(vec) - 1 while(l < r): if vec[i] + vec[l] + vec[r] == sum: return True elif vec[i] + vec[l] + vec[r] < sum: l += 1 else: # vec[i] + vec[l] + vec[r] > sum r -= 1 # If we reach here, then # no triplet was found return False# Driver codeif __name__ == '__main__': """ Let us create following BST 50 / \ 30 70 / \ / \ 20 40 60 80 """ root = Node(50) insert(root, 30) insert(root, 20) insert(root, 40) insert(root, 70) insert(root, 60) insert(root, 80) sum = 120 if (checkForTriplet(root, sum)): print("YES") else: print("NO")# This code is contributed by MRINALWALIA |
C#
// C# program to check if a triplet with// given SUM exists in the BST or notusing System;using System.Collections.Generic;class GFG{class Node { public int key; public Node left, right;};// A utility function to // create a new BST nodestatic Node newNode(int item){ Node temp = new Node(); temp.key = item; temp.left = temp.right = null; return temp;}// A utility function to do inorder traversal// of the BST and store values in a vectorstatic void inorder(Node root, List<int> vec){ if (root != null) { inorder(root.left, vec); vec.Add(root.key); inorder(root.right, vec); }}// A utility function to insert a new node// with given key in BSTstatic Node insert(Node node, int key){ /* If the tree is empty, return a new node */ if (node == null) return newNode(key); /* Otherwise, recur down the tree */ if (key < node.key) node.left = insert(node.left, key); else if (key > node.key) node.right = insert(node.right, key); /* return the (unchanged) node pointer */ return node;}// Function to check if a triplet with // given SUM exists in the BST or notstatic bool checkForTriplet(Node root, int sum){ // List to store the inorder traversal // of the BST List<int> vec = new List<int>(); // Call inorder() to do the inorder // on the BST and store it in vec inorder(root, vec); // Now, check if any triplet with given sum // exists in the BST or not int l, r; // Now fix the first element one by one // and find the other two elements for (int i = 0; i < vec.Count - 2; i++) { // To find the other two elements, // start two index variables from two corners // of the array and move them toward each other l = i + 1; // index of the first element in the // remaining elements // index of the last element r = vec.Count - 1; while (l < r) { if (vec[i] + vec[l] + vec[r] == sum) { return true; } else if (vec[i] + vec[l] + vec[r] < sum) l++; else // vec[i] + vec[l] + vec[r] > sum r--; } } // If we reach here, // then no triplet was found return false;}// Driver Codepublic static void Main(String[] args){ /* Let us create following BST 50 / \ 30 70 / \ / \ 20 40 60 80 */ Node root = null; root = insert(root, 50); insert(root, 30); insert(root, 20); insert(root, 40); insert(root, 70); insert(root, 60); insert(root, 80); int sum = 120; if (checkForTriplet(root, sum)) Console.Write("YES"); else Console.Write("NO");}} |
Javascript
<script>// Javascript program to check if a triplet with// given SUM exists in the BST or notclass Node { constructor() { this.key = 0; this.left = null; this.right = null; }};// A utility function to // create a new BST nodefunction newNode(item){ var temp = new Node(); temp.key = item; temp.left = temp.right = null; return temp;}// A utility function to do inorder traversal// of the BST and store values in a vectorfunction inorder(root, vec){ if (root != null) { inorder(root.left, vec); vec.push(root.key); inorder(root.right, vec); }}// A utility function to insert a new node// with given key in BSTfunction insert(node, key){ /* If the tree is empty, return a new node */ if (node == null) return newNode(key); /* Otherwise, recur down the tree */ if (key < node.key) node.left = insert(node.left, key); else if (key > node.key) node.right = insert(node.right, key); /* return the (unchanged) node pointer */ return node;}// Function to check if a triplet with // given SUM exists in the BST or notfunction checkForTriplet(root, sum){ // List to store the inorder traversal // of the BST var vec = []; // Call inorder() to do the inorder // on the BST and store it in vec inorder(root, vec); // Now, check if any triplet with given sum // exists in the BST or not var l, r; // Now fix the first element one by one // and find the other two elements for (var i = 0; i < vec.length - 2; i++) { // To find the other two elements, // start two index variables from two corners // of the array and move them toward each other l = i + 1; // index of the first element in the // remaining elements // index of the last element r = vec.length - 1; while (l < r) { if (vec[i] + vec[l] + vec[r] == sum) { return true; } else if (vec[i] + vec[l] + vec[r] < sum) l++; else // vec[i] + vec[l] + vec[r] > sum r--; } } // If we reach here, // then no triplet was found return false;}// Driver Code/* Let us create following BST 50 / \ 30 70 / \ / \ 20 40 60 80 */var root = null;root = insert(root, 50);insert(root, 30);insert(root, 20);insert(root, 40);insert(root, 70);insert(root, 60);insert(root, 80);var sum = 120;if (checkForTriplet(root, sum)) document.write("YES");else document.write("NO");// This code is contributed by itsok.</script> |
Output
YES
Complexity Analysis:
- Time Complexity: O(N2), as we are using nested loops, the outer loop traverses N times and the inner loop traverses N times in the worst case.
- Auxiliary Space: O(N), where N is the number of nodes in the given BST. (as we are using extra space for the tree)
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!
