Do you think IIT Guwahati certified course can help you in your career?
No
Introduction
Hey, Ninja! Are you confident about your understanding of binary search trees? Unleash your inner problem-solver and get ready to tackle a new challenge. The task at hand? Finding a triplet of values in a BST that adds up to a given sum, but with a twist – doing it in the most efficient way possible. This article will discover the solution to the problem "Check if a triplet with the given sum exists in a binary search tree." Buckle up and get ready to add a new feather to your BST problem-solving cap!
You will get a binary search tree and a sum as input. Your task is to determine whether there is any triplet sum (a sum of three elements) that equals the required sum.
Explanation
Consider the following example to understand the problem better.
Given BST:
Given Sum: 136
Expected Output: YES, Triplet Sum EXISTS!
Explanation: The sum of 11, 44, and 81 is 136. Hence, a triplet with the given sum exists in BST.
Now that we understand the problem, let's move further to learn about its solution. But before that, we'll review some concepts we will use to solve this problem.
Let us build on the momentum with a brief discussion about binary search trees.
Approach 1
The question is similar to finding a triplet with the given sum in an array. The only difference is that instead of an array, we have a binary search tree. That makes one thing clear; we must traverse the tree at least once and store the traversal in an array. After that, the question reduces to a basic problem, that is, finding a triplet with the given sum in an array.
We can use the in-order traversal to get the nodes in ascending order to find a triplet with the given sum in a binary search tree (BST). Then, we can use the two-pointers approach, where one pointer starts from the smallest element, and the other pointer starts from the largest element. We compare the sum of the elements pointed out by these pointers with the given sum. We have found the triplet if the sum is equal to the given sum. If the sum of these elements is lesser than the given sum, we move the pointer to the smaller element toward the right. If the sum exceeds the given sum, we move the pointer to the larger element toward the left. We repeat these steps until we find a triplet with the given sum or until the two pointers meet.
Note: It's always helpful to try out different inputs and outputs before moving on to the solution. This way, you can clearly understand the problem and come up with a solution on your own.
Now we will look at the algorithm that will help us to code this approach.
Algorithm
The algorithm for the above-discussed approach is as follows:
Perform Inorder traversal on the given binary tree and store it in an array (say arr).
Create two variables (say leftSum and rightSum) that will store two of the three elements required to make the triplet sum.
Now iterate the created array from 0 up to size - 2
In every iteration, initialize leftSum to i+1 and rightSum to size-1.
While the leftSum is less than the rightSum, check:
If arr[i] + arr[leftSum] + arr[rightSum] is equal to the required sum, return true.
Else, if arr[i] + arr[leftSum] + arr[rightSum] is less than the required sum, increase leftSum by one.
Else, increase rightSum by one.
If the loops are exhausted, and the triplet sum is not found, return false.
You must wonder why we’re iterating till size-2 and not till size-1. Let's clear it up for you.
When we iterate over an array to find triplets that sum up to a given value, we stop at the second last element (size - 2) because we need to have at least two elements to the right of a current element to form a triplet. If we were to iterate up to the last element (size - 1), we would end up considering the last element of the array as one of the left or right elements of a triplet, leading to incorrect results.
Now to visualize the algorithm, let’s try a dry run.
Dry Run
Consider the following BST to find a triplet with the given sum:
Sum: 136
The first step is storing the in-order traversal in an array. The array (arr) containing the in-order traversal will look like this.
We will initialize i=0, leftSum = 1, and rightSum = 8. These variables will work as pointers in our array. Their initial positions will look like this.
The Python implementation to check if a triplet with the given sum exists in BST is as follows.
Python
class Node:
def __init__(self, data):
self.data = data
self.rightChild = self.leftChild = None
def insert(root, x):
if root is None:
root = Node(x)
else:
if root.data < x:
if root.rightChild is None:
root.rightChild = Node(x)
else:
insert(root.rightChild, x)
else:
if root.leftChild is None:
root.leftChild = Node(x)
else:
insert(root.leftChild, x)
def inorder(root, ior):
if root is None:
return
inorder(root.leftChild, ior)
ior.append(root.data)
inorder(root.rightChild, ior)
def findTriplet(root, sum):
vect = [0]
inorder(root, vect)
for i in range(0, len(vect) - 2, 1):
l = i + 1
r = len(vect) - 1
while l < r:
if vect[i] + vect[l] + vect[r] == sum:
return True
elif vect[i] + vect[l] + vect[r] < sum:
l += 1
else:
r -= 1
return False
# Driver code
if __name__ == "__main__":
root = Node(55)
insert(root, 44)
insert(root, 36)
insert(root, 11)
insert(root, 45)
insert(root, 80)
insert(root, 74)
insert(root, 85)
insert(root, 81)
sum = 135
if findTriplet(root, sum):
print("YES, Triplet Sum EXISTS!")
else:
print("NO, Triplet Sum does not EXIST!")
Output
Let us now discuss the time and space complexity of these codes.
Complexity Analysis
Time Complexity
O(n2) is the time complexity of the above codes to find a triplet with the given sum in BST, where n is the number of nodes in the binary search tree (BST).
Reason:
The time complexity of the codes depends on two main operations:
The in-order traversal of BST to store its elements in a vector. In the worst case, the in-order traversal has a time complexity of O(n), where n is the number of elements in the BST.
Finding the triplet sum in the vector. We are using a nested loop, where the outer loop takes O(n) time, and the inner loop takes O(n) time in the worst case.
Therefore, the time complexity of finding the triplet with the given sum is O(n2).
Space Complexity
The space complexity of the above codes to find a triplet with the given sum in a BST is O(n), where n is the number of elements in the binary search tree.
Reason:
The space complexity of this code can be analyzed as follows:
The space for creating the BST is O(n), where n is the number of nodes in the tree. That is because each node in the tree requires space to store its data and pointers to its left and right children.
The space required to store the in-order traversal of the BST in a vector is O(n). That is because the in-order traversal visits each node in the tree, so the vector's size will equal the number of nodes in the tree.
The space required for the two pointers, leftSum, and rightSum, used in the findTriplet method is O(1). These pointers only take up a constant amount of space, regardless of the input size.
In total, the space complexity of the above codes is O(n), as the space requirements of the BST, the in-order traversal vector, and the two pointers all add up to a space requirement proportional to the size of the input.
Let us move further to learn another approach to solving this problem.
Another space-efficient approach to solving this problem is by using the two-pointer technique and only using a stack to traverse the BST without creating an additional array to store the traversal. Using this approach, we can solve the problem while reducing the extra space complexity to O(H), where H is the height of the BST.
Here's how this approach works:
We traverse the entire BST one node at a time.
For each node, we use two pointers to try and find a pair of nodes in the BST that add up to the target sum (sum - current->data), where curr is the current node we are traversing.
If we find such a pair, we have a triplet, and we can return it.
Consider the following example to help you understand what values will make up the required triplet.
We know that the required triplet will be formed from the sum of three values, say, x, y, and z. We can put this statement as:
x+y+z = sum
Now, assume that here current->data may contribute to forming the required triplet with the given sum. Don't get confused! current-> data is nothing but the data value of the node we are traversing.
Let’s replace it with x. We can write this as:
current->data + y + z = sum
Can we now write this as follows?
y + z = sum - current->data
Now, this y + z is the pair we must find out from our tree that will complete the required triplet. We'll figure it out with the two-pointer approach and stack.
How? Let’s find out.
The following algorithm will help us code this approach.
Algorithm
To implement this approach, we'll make two functions: hasPair and hasTriplet. The hasTriplet function will be called from the main function.
The algorithm for the hasTriplet function is as follows:
If the current node is null, return false.
Check if a pair exists in the binary search tree with sum equal to sum minus the current node's value by calling the hasPair function with root and sum - current.value as arguments.
If a pair with sum equal to sum minus the current node's value exists, return true.
If a pair with sum equal to sum minus the value of the current node does not exist, recursively search for a triplet in the left and right subtrees of the current node. It is done by calling the hasTriplet function with root, current.leftChild, and sum as arguments, and then with root, current.rightChild, and sum as arguments.
If no such pair is found, return false.
The algorithm for the hasPair function is as follows:
Initialize two stack iterators for traversal of the binary search tree. Create two empty stacks called forward and backward.
Initialize the forward iterator by setting the current node to the root node. While the current node is not null, push the current node onto the forward stack, then move to its left child.
Initialize the backward iterator by setting the current node to the root node. While the current node is not null, push the current node onto the backward stack, then move to its right child.
Use the two stack iterators to traverse the tree and find the pair of nodes that add up to the given sum. While both stacks are not empty, do the following:
Store the value of the top element in the forward stack as value1. And the value of the top element in the backward stack as value2.
If value1 + value2 == sum, return true.
If value1 > value2, break out of the loop because there can be no more pairs with a sum equal to the given sum.
If value1 + value2 > sum, pop the top element from the backward stack, move to its left child, and push all nodes on the path to the right onto the backward stack.
If value1 + value2 < sum, pop the top element from the forward stack, move to its right child, and push all nodes on the path to the left onto the forward stack.
If no pair is found, return false.
Consider the following dry run to visualize the algorithm.
Dry Run
Consider the following BST to find a triplet with the given sum:
The dry run is as follows:
First, the hasTriplet function will be called with 55, 55, 170 (root, root, sum) as the arguments.
Inside the hasTriplet function:
Initially, root = 55, current = 55, and sum = 170.
We’ll check if current = null [55 != null], which is false, so we’ll move further.
The following condition calls the hasPair function with 55, 115 (root, sum - current.value) as arguments.
Now inside the hasPair function:
Two stacks(forward and backward) of treeNode (structure of the tree)data type will be created to store the tree's left and right nodes.
Note that a complete node will be stored in the stack (including the addresses of its left and right child). The following representation shows only the data value stored in these nodes.
Now a while loop will begin to execute. It will run until either the forward and backward stacks become empty or a pair of values that equals the given sum is found.
1st iteration of the while loop:
Value1 will be initialized with the data value of the node, which is at the top of the forward stack. Value2 will be initialized with the data value of the node, which is at the top of the backward stack.
After this, we’ll check if value1 + value2 = sum, which is false since 96 < 115. So we’ll move forward.
After this, we’ll check if value1 > value2, which is false since 11 < 85. So we’ll move forward.
The next step is to check if value1 + value2 > sum, which is false since 96 < 115. So, the else part will get executed.
We’ll store the left child of the node that is on top of the forward stack in the current.
Now, we’ll pop the top node from the forward stack.
The condition for another while loop (current!= null) will be checked. Since current = null, this loop will not execute.
The forward and backward stacks now look like this:
Since none of these stacks are empty, we’ll move to another iteration of the initial while loop.
2nd iteration of the while loop:
The variable value1 will store the data value of node, which is at the top of the forward stack. And the variable value2 will store the data value of the node, which is at the top of the backward stack.
After this, we’ll check if value1 + value2 = sum, which is true since value1 + value2 = 115, which equals sum. So the function will return true.
Since the hasPair function returned true, the hasTriplet function will also return true.
Since the hasTriplet function returned true, we’ll print “Yes. triplet sum exists.” on the screen.
Let us now look at the implementation of this approach.
Implementation
Following is the implementation of the above discussed approach in Java, C++, and Python.
Java
import java.util.Stack;
class Main {
// Define a node structure for the binary tree
static class TreeNode {
int value;
TreeNode leftChild, rightChild;
// constructor.
public TreeNode(int value) {
this.value = value;
this.leftChild = null;
this.rightChild = null;
}
}
// Function to create a node of the tree
static TreeNode newNode(int item) {
TreeNode temp = new TreeNode(item);
return temp;
}
/*
Function to insert a new node
to the binary search tree
*/
static TreeNode insert(TreeNode node, int data) {
// If the BST is empty, return a new node
if (node == null) {
return newNode(data);
}
// Otherwise, recur down the tree
if (data < node.value) {
node.leftChild = insert(node.leftChild, data);
}
else if (data > node.value) {
node.rightChild = insert(node.rightChild, data);
}
return node;
}
/*
Function to find a pair in
the given binary search tree
with sum equal to the given sum
*/
static boolean hasPair(TreeNode root, int sum) {
/*
Initialize two stack iterators
for traversal of the binary
search tree
*/
Stack < TreeNode > forward = new Stack < > ();
Stack < TreeNode > backward = new Stack < > ();
// Initialize the forward iterator.
TreeNode current = root;
while (current != null) {
forward.push(current);
current = current.leftChild;
}
// Initialize the backward iterator
current = root;
while (current != null) {
backward.push(current);
current = current.rightChild;
}
// Two-pointer technique to find the pair
while (!forward.empty() && !backward.empty()) {
/*
Get the values of the top
elements in the stacks
*/
int value1 = forward.peek().value;
int value2 = backward.peek().value;
/*
If the sum of the values
of the top elements is equal
to sum, return true
*/
if (value1 + value2 == sum)
return true;
/*
If the value from the forward iterator
is greater than the value from the backward iterator,
then there can be no more pairs with a sum equal to the
given sum, so we break out of the loop
*/
if (value1 > value2)
break;
/*
Move the backward iterator
to the leftChild, if the
sum is more than given sum
*/
if (value1 + value2 > sum) {
current = backward.peek().leftChild;
backward.pop();
while (current != null) {
backward.push(current);
current = current.rightChild;
}
}
/*
Move the forward iterator
to the rightChild if the
sum is less than given sum
*/
else {
current = forward.peek().rightChild;
forward.pop();
while (current != null) {
forward.push(current);
current = current.leftChild;
}
}
}
// If no pair is found, return false
return false;
}
/*
Function to find the triplet
with the given sum in a BST
*/
static boolean hasTriplet(TreeNode root, TreeNode current, int sum) {
/*
If the current node is NULL,
there is no triplet with a sum
equal to the given sum
*/
if (current == null) {
return false;
}
/*
Check if there exists a pair in the
BST with a sum equal to the given sum
minus the value of the current node
*/
else if (hasPair(root, sum - current.value)) {
return true;
}
/*
If a pair with a sum equal to the given sum
minus the value of the current node
does not exist, recursively search for
the triplet in the left and right subtrees
of the current node
*/
else {
return hasTriplet(root, current.leftChild, sum) || hasTriplet(root, current.rightChild, sum);
}
}
public static void main(String[] args) {
TreeNode root = null;
root = insert(root, 55);
insert(root, 44);
insert(root, 30);
insert(root, 11);
insert(root, 45);
insert(root, 80);
insert(root, 74);
insert(root, 85);
insert(root, 81);
int sum = 170;
if (hasTriplet(root, root, sum)) {
System.out.println("YES, Triplet sum exists.");
} else {
System.out.println("NO, Triplet sum doesn't exist.");
}
}
}
Output
C++
#include <bits/stdc++.h>
using namespace std;
/*
Define a node structure
for the binary tree
*/
typedef struct treeNode {
int value;
struct treeNode * leftChild;
struct treeNode * rightChild;
}tree;
// Function to create a node of the tree
tree * newNode(int item) {
tree * temp = new tree;
temp -> value = item;
temp -> leftChild = temp -> rightChild = NULL;
return temp;
}
/*
Function to insert a new node
to the binary search tree
*/
tree * insert(tree * node, int data) {
// If the BST is empty, return a new node
if (node == NULL) {
return newNode(data);
}
// Otherwise, recur down the tree
if (data < node -> value) {
node -> leftChild = insert(node -> leftChild, data);
}
else if (data > node -> value) {
node -> rightChild = insert(node -> rightChild, data);
}
return node;
}
/*
Function to find a pair in
the given binary search tree
with sum equal to the given sum
*/
bool hasPair(tree * root, int sum) {
/*
Initialize two stack iterators
for traversal of the binary
search tree
*/
stack < tree * > forward, backward;
// Initialize the forward iterator
tree * current = root;
while (current != NULL) {
forward.push(current);
current = current -> leftChild;
}
// Initialize the backward iterator
current = root;
while (current != NULL) {
backward.push(current);
current = current -> rightChild;
}
// Two-pointer technique to find the pair
while (!forward.empty() && !backward.empty()) {
/*
Get the values of the top
elements in the stacks
*/
int value1 = forward.top() -> value;
int value2 = backward.top() -> value;
/*
If the sum of the values
of the top elements is equal
to sum, return true.
*/
if (value1 + value2 == sum) {
return true;
}
/*
If the value from the forward iterator
is greater than the value from the backward iterator,
then there can be no more pairs with a sum equal to the
given sum, so we break out of the loop
*/
if (value1 > value2) {
break;
}
/*
Move the backward iterator
to the leftChild, if the sum
is greater than the given sum
*/
if (value1 + value2 > sum) {
current = backward.top() -> leftChild;
backward.pop();
while (current != NULL) {
backward.push(current);
current = current -> rightChild;
}
}
/*
Move the forward iterator
to the rightChild if the
sum is less than given sum
*/
else {
current = forward.top() -> rightChild;
forward.pop();
while (current != NULL) {
forward.push(current);
current = current -> leftChild;
}
}
}
// If no pair is found, return false
return false;
}
/*
Function to find the triplet
with the given sum in a BST
*/
bool hasTriplet(tree * root, tree * current, int sum) {
/*
If the current node is NULL,
there is no triplet with
a sum equal to the given sum
*/
if (current == NULL) {
return false;
}
/*
Check if there exists a pair
in the BST with a sum equal to the given sum
minus the value of the current node
*/
else if (hasPair(root, sum - current -> value)) {
return true;
}
/*
If a pair with a sum equal to the given sum
minus the value of the current node
does not exist, recursively search for a
the triplet in the left and right subtrees
of the current node
*/
else {
return hasTriplet(root, current -> leftChild, sum) || hasTriplet(root, current -> rightChild, sum);
}
}
int main() {
tree * root = NULL;
root = insert(root, 55);
insert(root, 44);
insert(root, 30);
insert(root, 11);
insert(root, 45);
insert(root, 80);
insert(root, 74);
insert(root, 85);
insert(root, 81);
int sum = 170;
if (hasTriplet(root, root, sum)) {
cout << "YES, Triplet sum exists.";
} else {
cout << "NO, Triplet sum doesn't exist.";
}
return 0;
}
You can also try this code with Online C++ Compiler
# Define a node structure for the binary tree.
class TreeNode:
def __init__(self, value):
self.value = value
self.leftChild = None
self.rightChild = None
# Function to create a node of the tree
def newNode(item):
temp = TreeNode(item)
return temp
"""
Function to insert a new node
to the binary search tree
"""
def insert(node, data):
# If the BST is empty, return a new node
if node is None:
return newNode(data)
# Otherwise, recur down the tree
if data < node.value:
node.leftChild = insert(node.leftChild, data)
elif data > node.value:
node.rightChild = insert(node.rightChild, data)
return node
"""
Function to find a pair in
the given binary search tree
with sum equal to x
"""
def hasPair(root, sum):
"""
Initialize two stack iterators
for traversal of the binary
search tree
"""
forward = []
backward = []
# Initialize the forward iterator
current = root
while current is not None:
forward.append(current)
current = current.leftChild
# Initialize the backward iterator
current = root
while current is not None:
backward.append(current)
current = current.rightChild
# Two-pointer technique to find the pair
while len(forward) != 0 and len(backward) != 0:
"""
Get the values of the top
elements in the stacks
"""
value1 = forward[-1].value
value2 = backward[-1].value
if value1 + value2 == sum:
return True
"""
If the value from the forward iterator
is greater than the value from the backward iterator,
then there can be no more pairs with a sum equal to the
given sum, so we break out of the loop
"""
if value1 > value2:
break
"""
Move the backward iterator
to the leftChild if the
the sum is greater than the given sum
"""
if value1 + value2 > sum:
current = backward[-1].leftChild
backward.pop()
while current is not None:
backward.append(current)
current = current.rightChild
else:
current = forward[-1].rightChild
forward.pop()
while current is not None:
forward.append(current)
current = current.leftChild
# If no pair is found, return false
return False
"""
Function to find the triplet
with the given sum in a BST
"""
def hasTriplet(root, current, sum):
if current is None:
"""
If the current node is None,
there is no triplet with a sum
equal to the given sum
"""
return False
elif hasPair(root, sum - current.value):
"""
Check if there exists a pair in
the BST with a sum equal to given
sum minus the value of the current node
"""
return True
else:
"""
If a pair with a sum equal to given
sum minus the value of the current
node does not exist, recursively search
for a triplet in the left and right
subtrees of the current node
"""
return hasTriplet(root, current.leftChild, sum) or hasTriplet(root, current.rightChild, sum)
if __name__ == "__main__":
root = None
root = insert(root, 55)
insert(root, 44)
insert(root, 30)
insert(root, 11)
insert(root, 45)
insert(root, 80)
insert(root, 74)
insert(root, 85)
insert(root, 81)
sum = 170
if hasTriplet(root, root, sum):
print("YES, Triplet sum exists.")
else:
print("NO, Triplet sum doesn't exist.")
Output
Let us now do a quick complexity analysis of this approach.
Complexity Analysis
Following are the time and space complexities of this code.
Time Complexity
O(n2) is the time complexity of this code.
Reason: The time complexity of this code can be analyzed as follows:
The time complexity of the hasPair function is O(n), where n is the number of nodes in the tree.
The time complexity of the hasTriplet function is O(n2), where n is the number of nodes in the tree. It is because, for each node in the tree, we call the hasPair function.
Therefore, the overall time complexity of the code becomes O(n2).
Space Complexity
O(h) is the space complexity of this code, where h is the tree's height.
Reason:
The space complexity of this code can be analyzed as follows.
The space complexity of the hasPair function is O(h), where h is the tree's height. It is because we use two stacks to store the nodes, and the maximum size of these stacks is h.
The space complexity of the hasTriplet function is O(h), where h is the tree's height. Because the hasPair function takes O(h) space, and we call it for each node in the tree, the maximum space required is proportional to the tree's height.
Therefore, the overall space complexity of the code becomes O(h).
Let us now address some of the frequently asked questions.
Frequently Asked Questions
What do you mean by a Binary Search Tree?
A binary search tree (BST) is a data structure that stores data in a tree format. For any node in the tree, all elements in its left subtree are lesser than the node's key, and all elements in its right subtree are greater than the node's key.
What does a triplet sum in a BST mean?
The sum of the elements of any three nodes of a Binary Search Tree is called a triplet sum in a BST.
What is tree traversal?
Tree traversal refers to visiting all the nodes in a tree data structure in a specific order.
What is In-order traversal in a BST?
In an in-order traversal of a BST, we visit the nodes in the order of increasing values. First, we explore the left subtree, after that, the root node, and at last, the right subtree.
What is Pre-order traversal in a BST?
In a pre-order traversal of a BST, we visit the root node first, followed by the nodes in the left subtree, and then the nodes in the right subtree.
Conclusion
In this article, we learned about the solution to a famous problem of “checking if a triplet with the given sum exists in BST.” We also learned about its implementation in popular programming languages and their complexity analysis.
You can refer to the following articles to learn more about tree data structure.