Binary Search Trees: Find triplet sum in BST

Problem Statement:

You are given a BST node and a key.

YOu need to find if that key exist any triplet sum in given BST.

Solution

We do in-order traversal of the BST, we get the sorted order and store in an array.

Then we have reduced the problem to check if triplet sum exist or not and solve it.

Solution in C++

#include<iostream>
#include<vector>
#include<string>
#include<unordered_set>

using namespace std;


struct Node
{
    int data;
    struct Node *left, *right;
};

Node *get_new_node(int item)
{
    Node *temp =  new Node;
    temp->data = item;
    temp->left = temp->right = NULL;
    return temp;
}
 
Node* insert_into_bst(Node* node, int data) 
{ 
    if (node == NULL) return get_new_node(data); 
  
    if (data < node->data) 
        node->left  = insert_into_bst(node->left, data); 
    else if (data > node->data) 
        node->right = insert_into_bst(node->right, data);    
  
    return node; 
} 

void print_inorder(Node* Node) 
{ 
    if (Node == NULL) 
        return; 
    print_inorder(Node->left); 
    cout<<" "<<Node->data; 
    print_inorder(Node->right); 
} 

void store_inorder(Node* Node, vector<int> &vec) 
{ 
    if (Node != NULL){ 
    store_inorder(Node->left, vec); 
    vec.push_back(Node->data); 
    store_inorder(Node->right, vec); 
  }
} 

bool check_for_triplet(Node* root, int sum)
{

    vector<int> vec;
  
    store_inorder(root, vec);

    int l, r;
  
    for (int i = 0; i < vec.size() - 2; i++) {
  
        l = i + 1; 
  
        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 
                r--;
        }
    }
  
    return false;
}


int main()
{
    Node *root_1 = NULL; 
    root_1 = insert_into_bst(root_1, 1); 
    insert_into_bst(root_1, 2); 
    insert_into_bst(root_1, 3); 
    insert_into_bst(root_1, 4); 
    insert_into_bst(root_1, 5); 

    if (check_for_triplet(root_1, 12) == true)
        cout << "Yes, BST has a triplet sum " << endl;
    else
        cout << "No, BST does not have triplet sum " << endl;
    return 0;
}

Output:

Yes, BST has a triplet sum