1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Approach
2.1.
Algorithm
2.2.
Implementation in Java
2.3.
Implementation in C++
2.3.1.
Time Complexity
2.3.2.
Space Complexity
3.
Optimized Approach
3.1.
Algorithm to find Pair with given sum in Balanced BST
3.2.
Implementation in Java
3.3.
Implementation in C++
3.3.1.
Time Complexity
3.3.2.
Space Complexity
4.
4.1.
What is a Binary Tree?
4.2.
What is tree traversal?
4.3.
What is AVL Tree?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Pair with given sum in Balanced BST

Ayush Mishra
1 upvote

## Introduction

A data structure is a specialized format used to organize, process, retrieve, and store data. Several types of data structures, both basic and advanced, are all intended to organize data for a specific purpose.

This blog will discuss the problem of implementing Pair with a given sum in a Balanced Binary Search Tree in Data Structure. We will discuss this article in detail. Let’s start going!

### Problem Statement

In this problem, we are given a sum as input, and we have to find the two node pair whose key value sum is equal to the given sum in the Balanced Binary Search Tree (BST) without any modification.

With some examples, let’s understand the problem pair with a given sum in the Balanced Binary Search Tree ( BST).

### Sample Examples

Example 1:

Input:

``sum = 60``

Output:

`` Pair with the given sum is found (25,35)``

Explanation:

We will store the node of the tree in a set while traversing. If for present node 25, there exists a node for which the sum of both nodes is equal to the target node, then we will return the pair.

Example 2:

Input:

`` sum = 18``

Output:

``Pair with the given sum is found (8,10)``

Explanation:

We will store the node of the tree in a set while traversing. If for present node 8, there exists a node for which the sum of both nodes is equal to the target node, then we will return the pair.

## Approach

We will find the Pair by creating an auxiliary array and storing the Inorder traversal of Balanced BST in the array. The array will be sorted because BST inorder traversal always produces sorted data. We can pair in O(n) time once we have the Inorder traversal.

### Algorithm

1️⃣ Firstly, create a function to create a new Balanced BST node.

2️⃣ Create a function to check whether Pair exists or not.

3️⃣ Create an ArrayList inside the function to store the in-order traversal of nodes.

4️⃣ If the node is found, then the Pair exists. Otherwise, it does not exist.

### Implementation in Java

``````import java.util.*;
class Node {

int data;
Node left, right;

Node(int d)
{
data = d;
left = right = null;
}
}

class BST
{
Node root;
BST()
{
root = null;
}

void inorder()
{
Utilinorder(this.root);
}

//function for inorder traversal of the tree
void Utilinorder(Node node)
{
if (node == null)
{
return;
}

Utilinorder(node.left);
System.out.print(node.data + " ");
Utilinorder(node.right);
}

// This method mainly calls insert_element()
void insert(int key)
{
root = insert_element(root, key);
}

/*In BST, a recursive function for inserting a new key. */
Node insert_element(Node root, int key)
{
if (root == null)
{
root = new Node(key);
return root;
}

/*Recure down the BST */
if (key < root.data)
{
root.left = insert_element(root.left, key);
}
else if (key > root.data)
{
root.right = insert_element(root.right, key);
}
return root;
}

ArrayList<Integer> treeToArrayList(Node node, ArrayList<Integer> list)
{
if (node == null)
{
return list;
}

treeToArrayList(node.left, list);
treeToArrayList(node.right, list);

return list;
}

boolean checkPair(Node node, int target)
{
ArrayList<Integer> a1 = new ArrayList<Integer>();
ArrayList<Integer> a2 = treeToArrayList(node, a1);
int s = 0;
int e = a2.size() - 1;

while (s < e)
{
if (a2.get(s) + a2.get(e) == target)
{
System.out.println("Pair with given sum is found: " + a2.get(s) + " + " + a2.get(e) + " "+ "= " + target);
return true;
}

if (a2.get(s) + a2.get(e) > target) // Decrement the End(e)
{
e--;
}

if (a2.get(s) + a2.get(e) < target) // Increment the Start(s)
{
s++;
}
}
System.out.println("No such values are found in Balanced BST!");
return false;
}

// Driver function
public static void main(String[] args)
{
BST balancetree= new BST();

balancetree.insert(20);
balancetree.insert(15);
balancetree.insert(30);
balancetree.insert(12);
balancetree.insert(18);
balancetree.insert(25);
balancetree.insert(35);

balancetree.checkPair(balancetree.root, 60);
}
}``````

Output:

``Pair with given sum is found: 25 + 35 = 60``

### Implementation in C++

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

class Node
{
public:
int data;
Node* left;
Node* right;

Node(int d)
{
data=d;
left=NULL;
right=NULL;
}
};

class BST
{

public:
Node *root;

BST()    // Constructor
{
root = NULL;
}

//function for inorder traversal of the tree
void Utilinorder(Node* node)
{
if (node == NULL)
{
return;
}

Utilinorder(node->left);
cout << node->data << " ";
Utilinorder(node->right);
}

void inorder()
{
Utilinorder(this->root);
}

/* In BST, a recursive function for inserting a new key*/
Node* insert_Element(Node* root, int data)
{
if (root == NULL)
{
root = new Node(data);
return root;
}

/* Recur down the tree */
if (data < root->data)
{
root->left = insert_Element(root->left, data);
}
else if (data > root->data)
{
root->right = insert_Element(root->right, data);
}

return root;
}

// This method mainly calls insert_Element()
void insert(int key)
{
root = insert_Element(root, key);
}

//Method for inserting values from a given Balanced BST into a vector.

vector<int> treeToArrayList(Node* node, vector<int>& list)
{
// Base Case
if (node == NULL)
{
return list;
}

treeToArrayList(node->left, list);
list.push_back(node->data);
treeToArrayList(node->right, list);

return list;
}

//Method that checks if there is a pair present

bool checkPair(Node* node, int target)
{
vector<int> a1;
vector<int> a2 = treeToArrayList(node, a1);
int s = 0;
int e = (int)a2.size() - 1;

while (s < e)
{
if (a2[s] + a2[e] == target)
{
cout << "Pair with given sum is found: " << a2[s] << " + " << a2[e] << " = " << target << '\n';
return true;
}

if (a2[s] + a2[e] > target)  // Decrement the End(e)
{
e--;
}

if (a2[s] + a2[e] < target) // Increment the Start(s)
{
s++;
}
}

cout << "No such values are found in Balanced BST\n";
return false;
}
};

// Driver function
int main()
{
BST *balancetree = new BST();

balancetree->insert(20);
balancetree->insert(15);
balancetree->insert(30);
balancetree->insert(12);
balancetree->insert(18);
balancetree->insert(25);
balancetree->insert(35);

balancetree->checkPair(balancetree->root, 60);
}``````

Output:

``Pair with given sum is found: 25 + 35 = 60``

#### Time Complexity

The time complexity of the above Approach for the problem of finding Pair with a given sum Balanced BST is O(n) as we are using two pointer approach method whose time complexity is O(n).

#### Space Complexity

The space complexity of the above Approach for the problem of finding Pair with a given sum Balanced BST is O(n). This complexity is due to the extra space required to create and store the Binary Search Tree.

Check out this problem - Pair Sum In Array.

## Optimized Approach

The best-optimized Approach is finding the Pair in the sorted array using two pointer approach.

In this approach, we traverse the Balanced Binary tree in normal and reverse in order simultaneously using the two pointer approach and if the sum is the same as the target sum, return true.

### Algorithm to find Pair with given sum in Balanced BST

🚀 Firstly, create a Balanced BST node.

🚀 Create a function isCheckPair() to check whether Pair exists or not.

🚀 Use two pointer approach to traverse the normal and reverse inorder simultaneously.

🚀 If the total exceeds the target, proceed to the next node in the reverse inorder traversal.

🚀 If the sum is less than the target, continue with the normal inorder traversal.

🚀 If the sum is equal to the target, the print pair exists.

### Implementation in Java

``````import java.util.*;
class Solutions
{

static class node
{
int val;
node left, right;
};

//function to check whether Pair exists or not

static boolean isCheckPair(node root, int target)
{
Stack<node> s1 = new Stack<node>();
Stack<node> s2 = new Stack<node>();

boolean d1 = false;
boolean d2 = false;
int val1 = 0, val2 = 0;
node curr1 = root, curr2 = root;

while (true)
{

while (d1 == false)
{
if (curr1 != null)
{
s1.push(curr1);
curr1 = curr1.left;
}
else
{
if (s1.isEmpty())
d1 = true;
else
{
curr1 = s1.pop();
val1 = curr1.val;
curr1 = curr1.right;
d1 = true;
}
}
}

while (d2 == false)
{
if (curr2 != null)
{
s2.push(curr2);
curr2 = curr2.right;
}

else {
if (s2.isEmpty())
d2 = true;

else {
curr2 = s2.pop();
val2 = curr2.val;
curr2 = curr2.left;
d2 = true;
}
}
}

if ((val1 != val2) && (val1 + val2) == target)
{
System.out.print("Pair with given sum is found: " +
val1+ "+ " +
val2+ " = " +
target +"\n");
return true;
}

else if ((val1 + val2) < target)
d1 = false;

else if ((val1 + val2) > target)
d2 = false;

if (val1 >= val2)
return false;
}
}

// A function to create a Balanced BST node

static node NewNode(int val)
{
node tmp = new node();
tmp.val = val;
tmp.right = tmp.left = null;
return tmp;
}

// Driver program to test the above functions
public static void main(String[] args)
{

node root = NewNode(20);
root.left = NewNode(15);
root.right = NewNode(30);
root.left.left = NewNode(12);
root.left.right = NewNode(18);
root.right.left = NewNode(25);
root.right.right = NewNode(35);

int target = 37;
if (isCheckPair(root, target) == false)
System.out.print("No such values are found");
}
}``````

Output:

``Pair with given sum is found: 12+ 25 = 37``

### Implementation in C++

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

class TreeNode {
public:
int val;
TreeNode *left, *right;
TreeNode(int data) {
val = data;
left = NULL;
right = NULL;
}
};

//function to check whether Pair is exist or not

bool isCheckPair(TreeNode* root, int target) {

stack<TreeNode*> s1, s2;
bool d1 = false;
bool d2 = false;
int val1 = 0, val2 = 0;
TreeNode *curr1 = root, *curr2 = root;
while (true) {
while (d1 == false) {
if (curr1 != NULL) {
s1.push(curr1);
curr1 = curr1->left;
}
else {
if (s1.empty())
d1 = 1;
else {
curr1 = s1.top();
s1.pop();
val1 = curr1->val;
curr1 = curr1->right;
d1 = 1;
}
}
}
while (d2 == false) {
if (curr2 != NULL) {
s2.push(curr2);
curr2 = curr2->right;
}
else {
if (s2.empty())
d2 = 1;
else {
curr2 = s2.top();
s2.pop();
val2 = curr2->val;
curr2 = curr2->left;
d2 = 1;
}
}
}
if ((val1 != val2) && (val1 + val2) == target) {
cout << "Pair with given sum is found: " << val1 << " + " << val2 << " = " << target << endl;
return true;
}
else if ((val1 + val2) < target)

d1 = false;
else if ((val1 + val2) > target)
d2 = false;
if (val1 >= val2)
return false;
}
}
// Driver function

int main() {
TreeNode* root = new TreeNode(20);
root->left = new TreeNode(15);
root->right = new TreeNode(30);
root->left->left = new TreeNode(12);
root->left->right = new TreeNode(18);
root->right->left = new TreeNode(25);
root->right->right = new TreeNode(35);
int target = 37;
isCheckPair(root, target);
}``````

Output:

``Pair with given sum is found: 12 + 25 = 37``

#### Time Complexity

The time complexity of the above Approach for the problem of finding Pair with a given sum Balanced BST is O(n) as we are using two pointer approach method whose time complexity is O(n).

#### Space Complexity

The space complexity of the above Approach for the problem of finding Pair with a given sum Balanced BST is O(logn) as we did not need to use extra space required for storing the BST.

### What is a Binary Tree?

A binary tree is a type of generic tree in which each node can only have two children. The root of the node, the left sub-tree, and the right binary sub-tree are the three disjoint subsets of a binary tree.

### What is tree traversal?

Tree traversal refers to the process of traversal all of the nodes in a tree. We always begin with the root (head) because it is the first node, and all nodes are connected via edges (or links). Inorder, Preorder, and Postorder traversals are three types of traversals in the tree data structure.

### What is AVL Tree?

The height balancing binary search trees known as AVL trees are named after their creators, Adelson, Velski, and Landis. The AVL tree compares the left and right subtree heights and ensures that the difference is less than one. This distinction is referred to as the Balance Factor.

BalanceFactor = height(left-subtree) − height(right-subtree)

## Conclusion

Congratulations on finishing the blog! We discussed the problem of finding the Pair with the given sum in Balanced BST. We use brute force and an optimized approach to implement this problem of the Balanced Binary Search Tree.

We hope this blog has helped you enhance your knowledge regarding the topic of Tree data structure, and if you want to learn more, then you can check articles on:-

Please refer to our guided pathways on Code studio to learn more about DSACompetitive ProgrammingJavaScriptSystem Design, etc. Enroll in our courses, and use the accessible sample exams and questions as a guide. For placement preparations, look at the interview experiences and interview package.

Please do upvote our blogs if you find them helpful and informative!

Happy learning!

Live masterclass