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);
list.add(node.data);
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 = 60Implementation 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.
84+ registered