Check if a triplet with given sum exists in BST

Aditya Narayan Joardar
Last Updated: May 13, 2022

Introduction

In this article, we are going to learn how to check if a triplet with a given sum exists in BST or not. Such problems are important as they help us understand many concepts related to the Tree data structure. A Binary Search Tree is a special kind of tree where each node has two child nodes such that the left child is smaller than the root node and the right child is greater than the root node. To find the triplet sum first, we need to access each node of the BST. We will be using one of the Traversal techniques, Inorder Traversal.  
It is highly recommended to have a basic idea of Binary TreesBinary Search Trees, and   Tree Traversals before proceeding with this problem.

Problem Statement

You have been provided with a Binary Search Tree and a Sum. Your task is to check whether there exists any triplet sum (summation of three elements) such that it is equal to the required Sum. 

Example

Consider the following Binary Search Tree

BST visualizer


Let the required sum be 135  
Expected Output: YES, Triplet Sum EXISTS! 
Explanation: Sum of 11, 44 and 80 is 135, hence we can say that a triplet with given sum exists in BST

Approach and Explanation

The question is quite similar to finding a triplet with a given sum in an array, the only difference is instead of an array we are having a binary search tree here. That makes one thing clear for sure, you have to traverse the tree at least once and store the traversal in an array, after the traversal is done the question reduces to finding a triplet with a given sum in an array which is a very basic problem. 

(Source: giphy)

Now the point is which traversal technique should be used and why? 
In an interview if you are stuck in such a problem, the best solution is to try out different combinations of input and output yourself. For example, in this question you can try finding the traversals of the BST and check which traversal suits the best for your problem. 
A common observation is when you try out finding traversals for BST, you will notice that the inorder traversal the values are sorted in increasing order. So we can use the inorder traversal in this case. 
In the above example, the inorder traversal will give [11, 36, 44, 45, 55, 74, 80, 81, 85]. The required sum is 135. The program returns true because the three elements [11, 44, 80] sum up to 135. If the required sum were 134, the output would have been false as there are no three such elements that sum up to 134.  I am sure you are curious to know how to solve this problem. It's recommended that you take a pen and paper and think of a possible solution on your own before moving on to the solution. Think out all the possible solutions and try to get a solution.  The given approach is for finding the triplet sum only. To know how to perform Inorder traversal goto, Inorder Traversal.  So without any further ado, let’s see the step-by-step approach. 

  • Perform Inorder traversal on the given binary tree and store it in an array (say arr).
  • Create two variables (say leftSum and rightSum) that will store two of the three elements required to make the triplet sum.
  • Now iterate the created array from 0 up to size - 2
    • In every iteration, initialize leftSum to i+1 and rightSum to size-1.
    • While the leftSum is less than the rightSum  check:
      1. If arr[i]arr[leftSum]arr[rightSum] is equal to the required sum, return true.
      2. Else if arr[i]arr[leftSum]arr[rightSum] is less than the required sum, increase leftSum by one.
      3. Else increase rightSum by one.
  • Once our while and for loops are exhausted, and the triplet sum is not found, return false.

Recommended: Try to write your code before proceeding to the solution code.

Java Implementation

The Java implementation to check if a triplet with a given sum exists in BST is given below:

import java.util.*;
public class TripletSum{
 static class BTNode
 {
     int data;
     BTNode leftChild, rightChild;
 }
 static BTNode newBTNode(int item)
 {
     BTNode tempBTNode = new BTNode();
     tempBTNode.data = item;
     tempBTNode.leftChild = tempBTNode.rightChild = null;
     return tempBTNode;
 }
 static BTNode insert(BTNode node, int data)
 {
     if (node == null)
         return newBTNode(data);
     if (data < node.data)
         node.leftChild = insert(node.leftChild, data);
     else if (data > node.data)
         node.rightChild = insert(node.rightChild, data);
     return node;
 }
 static void inorderTraversal(BTNode root, List<Integer> al)
 {
     if (root != null)
     {
         inorderTraversal(root.leftChild, al);
         al.add(root.data);
         inorderTraversal(root.rightChild, al);
     }
 }
 static boolean checkForTriplet(BTNode root, int sum)
 {
     List<Integer> al = new ArrayList<>();
     inorderTraversal(root, al);
     int leftSum, rightSum;
     for (int i = 0; i < al.size() - 2; i++)
     {
         leftSum = i + 1;
         rightSum = al.size() - 1;
         while (leftSum < rightSum)
         {
             if (al.get(i) + al.get(leftSum) + al.get(rightSum) == sum){
                 return true;
             }
             else if (al.get(i) + al.get(leftSum) + al.get(rightSum) < sum) {
                 leftSum++;
             }
             else
                 rightSum--;
         }
     }
     return false;
 }
 public static void main(String[] args)
 {
     /*
         Example BST
                     55
                   /     \
                 44       80
               /   \    /    \
             36    45  74     85
           /                /
           11               81
       */
     BTNode root = insert(null, 55);
     insert(root, 44);
     insert(root, 36);
     insert(root, 11);
     insert(root, 45);
     insert(root, 80);
     insert(root, 74);
     insert(root, 85);
     insert(root, 81);
     int sum = 135;
     if (checkForTriplet(root, sum))
         System.out.print("YES, Triplet Sum EXISTS!");
     else
         System.out.print("NO, Triplet Sum does NOT EXIST!");
 }
}

Output 
YES, Triplet Sum EXISTS!

C++ Implementation

The C++ implementation to check if a triplet with a given sum exists in BST is given below:

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
 
struct Node {
    int data;
    struct Node *leftChild, *rightChild;
};

struct Node* newNode(int item)
{
    Node* temp = new Node;
    temp->data = item;
    temp->leftChild = temp->rightChild = NULL;
    return temp;
}
 
void inorder(Node* root, vector<int>& vec)
{
    if (root != NULL) {
        inorder(root->leftChild, vec);
        vec.push_back(root->data);
        inorder(root->rightChild, vec);
    }
}

struct Node* insert(Node* node, int data)
{
    /* If the tree is empty, return a new node */
    if (node == NULL)
        return newNode(data);
 
    /* Otherwise, recur down the tree */
    if (data < node->data)
        node->leftChild = insert(node->leftChild, data);
    else if (data > node->data)
        node->rightChild = insert(node->rightChild, data);
 
    /* return the (unchanged) node pointer */
    return node;
}
bool checkForTriplet(Node* root, int sum)
{
    vector<int> vec;
    inorder(root, vec);
    int leftSum, rightSum;
 
    for (int i = 0; i < vec.size() - 2; i++) {
 
        leftSum = i + 1; 
        rightSum = vec.size() - 1;
        while (leftSum < rightSum) {
            if (vec[i] + vec[leftSum] + vec[rightSum] == sum) {
                return true;
            }
            else if (vec[i] + vec[leftSum] + vec[rightSum] < sum)
                leftSum++;
            else
                rightSum--;
        }
    }
     return false;
}
int main()
{
    /*
        Example BST


                       55
                    /     \
                  44       80
                /   \    /    \
              36    45  74     85
             /                /
            11               81
        
    */


    struct Node* root = NULL;
    root = insert(root, 55);
    insert(root, 44);
    insert(root,36);
    insert(root, 11);
    insert(root, 45);
    insert(root, 80);
    insert(root, 74);
    insert(root, 85);
    insert(root, 81);
    
    int sum = 135;
 
    if (checkForTriplet(root, sum))
        cout << "YES, Triplet Sum EXISTS!";
    else
        cout << "NO, Triplet Sum does not EXIST!";
 
    return 0;
}

Output

YES, Triplet Sum EXISTS!

Python Implementation

The Python implementation to check if a triplet with a given sum exists in BST is given below:

class Node:
    def __init__(self, data):
         
        self.data = data
        self.rightChild = self.leftChild = None
 
def insert(root, x):
 
    if root is None:
        root = Node(x)
     
    else:
        if root.data < x:
            if root.rightChild is None:
                root.rightChild = Node(x)
            else:
                insert(root.rightChild, x)
                 
        else:
            if root.leftChild is None:
                root.leftChild = Node(x)
            else:
                insert(root.leftChild, x)
def inorder(root, ior):
 
    if root is None:
        return
 
    inorder(root.leftChild, ior)
    ior.append(root.data)
    inorder(root.rightChild, ior)
 
def checkForTriplet(root, sum):
    vec = [0]
    inorder(root, vec)
    for i in range(0, len(vec) - 2, 1):
        l = i + 1
         
        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:
                r -= 1
          
    return False
 
# Driver code
if __name__ == '__main__':
    
    root = Node(55)
    insert(root, 44)
    insert(root, 36)
    insert(root, 11)
    insert(root, 45)
    insert(root, 80)
    insert(root, 74)
    insert(root, 85)
    insert(root, 81)


    sum = 135
     
    if (checkForTriplet(root, sum)):
        print("YES, Triplet Sum EXISTS!")
    else:
        print("NO, Triplet Sum does not EXIST!")
 

Output  
YES, Triplet Sum EXISTS!

Complexities

Time Complexity

In the given implementation, we select the first and last element, loop within them while the leftSum is less than rightSum to find the triplet sum. Thus, the time complexity is, T(n) = O(N2), where N is the number of nodes in the binary tree. 

Space Complexity

In the given implementation, we create a one-dimensional ArrayList to store the inorder traversal of the binary tree. Thus, Space complexity = O(N), where N is the number of nodes of the binary tree.

Frequently Asked Questions

  1. What does triplet sum in a BST mean?
    The sum of the elements of any three nodes of a Binary Search Tree is called a triplet sum. You can get a better understanding of triplet sum with the help of this problem, Smaller Than Triplet Sum
  2. Why do we perform Inorder Travsersal? 
    Out of all the tree traversal techniques, we choose Inorder traversal because the resultant array contains all the elements of the BST sorted in ascending order. In our implementation, the sorted array reduces the number of computations and finds the triplet sum faster.

Key Takeaways

To summarize the article, we discussed how to check if a triplet sith given sum exists in BST or not. We first familiarized ourselves with the problem statement, followed by an example. After understanding the example we jumped straight into our approach and a Java implementation. We also discussed the time and space complexities and addressed a few FAQs.  
Want to ace the coding rounds of big tech companies? Try our Attempt Unlimited Online Mock Test Series to start your preparation.Learn various topics from Web Technologies, Programming Fundamentals, Data Structures, and Algorithms from our Library.

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think