Binary Tree: Given a BST and a target, find if a pair exists

Problem Statement:

You are given a BST and a target, you need to find if such pair exist in the tree.

Example:

Input: 

target: 26

    /*
     *           10
     *         /    \
     *        8      12
     *       / \    /  \
     *      2   9  11   14
     */

Output:

True

Solution Explanation:

We will use inorder traversal and store the elements in the array.

As the array will be sorted, we will use map to find if both element exist or not and return the result.

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

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


struct Node* newNode(int data)
{
    struct Node* newNode = new Node;
    newNode->data = data;
    newNode->left = newNode->right = NULL;

    return (newNode);
}


void insert_inorder(Node* root, vector<int>&nodes)
{
    if(root==NULL)
    	return;

    insert_inorder(root->left,nodes);
    nodes.push_back(root->data);
    insert_inorder(root->right,nodes);
}
bool solution(Node* root, int k) 
{
    vector<int> nodes;
    insert_inorder(root,nodes);

    map<int,int>mp;
    
    for(int i=0; i<nodes.size(); i++)
    {
        auto it=mp.find(k-nodes[i]);

        if(it!=mp.end())
        {
            return true;
        }

        mp[nodes[i]]++;
    }
    return false;

}

int main(void)
{
    /*
     *           10
     *         /    \
     *        8      12
     *       / \    /  \
     *      2   9  11   14
     */
    struct Node* root = newNode(10);
    root->left = newNode(8);
    root->right = newNode(12);
    root->left->left = newNode(2);
    root->left->right = newNode(9);
    root->right->left = newNode(11);
    root->right->right = newNode(14);

    if (solution(root, 26))
    {
    	cout<<"True";
    }
    else
    {
    	cout<<"False";
    }

    return 0;
}

Output

True