# Find a Pair with the given sum in a BST

Posted in  Vinay Khatri
Last updated on June 8, 2022

## Problem

Given a binary tree, the task is to find a pair with the given sum. The elements of the tree are pairwise distinct.

#### Sample Input

```Sum = 11 ```

#### Sample Output

`Pair is (4, 7)`

## Approach

We will use an unordered set to solve this problem. This is because an unordered set gives the time complexity of O(1) if there are not many duplicates present in it. Since, in the BST, we have all values different, we can use this data structure for the solution. We traverse the tree and keep inserting the elements in the set. If we see that ( sum-current node) exists in the set, we have found the pair. Otherwise, we keep on searching the tree.

### Complexity Analysis

The time complexity would be O(N) as we are traversing the entire tree. The space complexity would be O(N) due to the call stack and auxiliary data structure.

### C++ Programming

```#include<bits/stdc++.h>
using namespace std;

struct TreeNode
{
int val;
TreeNode *left, *right;
};

// create new bode
TreeNode* newNode(int ele)
{
TreeNode* node = new TreeNode;
node->val = ele;
node->left = node->right = nullptr;

return node;
}

// insert new node
TreeNode* insert(TreeNode* root, int ele)
{
// if the root is null
if (root == nullptr) {
return newNode(ele);
}

// if the given ele is less than the root node
if (ele < root->val) {
root->left = insert(root->left, ele);
}

// if the given ele is more than the root node
else {
root->right = insert(root->right, ele);
}

return root;
}

bool solve(TreeNode* root, int sum, auto &us)
{
// base case
if (root == nullptr) {
return false;
}

// return true if pair is found in the left subtree
if (solve(root->left, sum, us)) {
return true;
}

// if the pair found
if (us.find(sum - root->val) != us.end())
{
cout << "Pair is (" << sum - root->val << ", " << root->val << ")";
return true;
}

// insert the current node's value into the set
else {
us.insert(root->val);
}

// search in the right subtree
return solve(root->right, sum, us);
}

int main()
{
int values[] = {1, 3, 4, 6, 7, 8, 10, 13, 14};

TreeNode* root = nullptr;

for (int ele: values) {
root = insert(root, ele);
}

int sum = 11;

unordered_set<int> us;

if (!solve(root, sum, us)) {
cout << "Pair not present";
}

return 0;
}```

#### Output

`Pair is (4, 7)`

### Java Programming

```import java.util.HashSet;
import java.util.Set;

class TreeNode
{
int val;
TreeNode left = null, right = null;

TreeNode(int val) {
this.val = val;
}
}

class Main
{
// insert nodes
public static TreeNode insert(TreeNode root, int ele)
{
// if the root is null, create node
if (root == null) {
return new TreeNode(ele);
}

// if the given ele is less than the root node
if (ele < root.val) {
root.left = insert(root.left, ele);
}

// if the given ele is more than the root node
else {
root.right = insert(root.right, ele);
}
return root;
}

public static boolean solve(TreeNode root, int sum, Set<Integer> us)
{
// base case
if (root == null) {
return false;
}

// return true if pair is found in the left subtree
if (solve(root.left, sum, us)) {
return true;
}

// if a pair is formed with the current node
if (us.contains(sum - root.val))
{
System.out.print("Pair is (" + (sum - root.val) + ", "
+ root.val + ")");
return true;
}

// insert the current node's value into the set
else {
}

// search in the right subtree
return solve(root.right, sum, us);
}

public static void main(String[] args)
{
int[] values = {1, 3, 4, 6, 7, 8, 10, 13, 14};

TreeNode root = null;
for (int ele: values) {
root = insert(root, ele);
}

int sum = 11;

// create an empty set
Set<Integer> us = new HashSet<>();

if (!solve(root, sum, us)) {
System.out.print("Pair not present");
}
}
}```

#### Output

`Pair is (4, 7)`

### Python Programming

```class TreeNode:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right

# insert keys into BST
def insert(root, key):
# if the root is None, create a new node
if root is None:
return TreeNode(key)

# if the given key is less than the root node
if key < root.val:
root.left = insert(root.left, key)

# if the given key is more than the root node
else:
root.right = insert(root.right, key)
return root

def check(root, sum, us):
# base case
if root is None:
return False

# return true if pair is found in the left subtree
if check(root.left, sum, us):
return True

# if a pair is formed with the current node
if sum - root.val in us:
print("Pair is", (sum - root.val, root.val))
return True

# insert the current node's value into the set
else:

# search in the right subtree
return check(root.right, sum, us)

keys = [1, 3, 4, 6, 7, 8, 10, 13, 14]

root = None

for key in keys:
root = insert(root, key)

sum = 11

# create an empty set
us = set()

if not check(root, sum, us):
print("Pair not present")```

#### Output

`Pair is (4, 7)`

## Conclusion

In this tutorial, we have used an unordered set to find a pair with the given sum, i.e., 11, in a binary tree, provided that the elements in the tree are pairwise distinct. We have implemented it in three different languages, namely Python, Java, and C++. Since all the elements in a tree are distinct, using an unordered set gives the time complexity of O(1). If you have any queries regarding the implementation of the above program, feel free to share them in the comments section below. People are also reading:

##### Tags:
b tree binary search tree tree