Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Explanation 
3.
Approach 1
3.1.
Algorithm
3.2.
Dry Run
3.3.
Implementation 
3.3.1.
Java
3.3.2.
Output
3.3.3.
C++
3.3.4.
Output
3.3.5.
Python
3.3.6.
Output
3.4.
Complexity Analysis
3.4.1.
Time Complexity
3.4.2.
Space Complexity
4.
Approach 2
4.1.
Algorithm
4.2.
Dry Run
4.3.
Implementation 
4.3.1.
Java
4.3.2.
Output
4.3.3.
C++
4.3.4.
Output
4.3.5.
Python
4.3.6.
Output
4.4.
Complexity Analysis
4.4.1.
Time Complexity
4.4.2.
Space Complexity
5.
Frequently Asked Questions
5.1.
What do you mean by a Binary Search Tree?
5.2.
What does a triplet sum in a BST mean?
5.3.
What is tree traversal?
5.4.
What is In-order traversal in a BST? 
5.5.
What is Pre-order traversal in a BST?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Check if a Triplet with given Sum Exists in BST

Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

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!

check if a triplet with given sum exits in BST

We recommend that you understand binary treesbinary search trees, and tree traversals thoroughly before proceeding with this problem.

Problem Statement

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:

bst example

 

Given Sum: 136

Expected Output: YES, Triplet Sum EXISTS!

triplet in bst example

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:

example BST

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.
dry run
  • 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.
dry run
  • Now, let’s check if (arr[i] + arr[leftSum] + arr[rightSum] = = Sum).
    arr[0] + arr[1] + arr[8] = 11 + 36 + 85 = 132.
    132 < Sum(136) 
    So, increment leftSum by 1.
dry run
  • Now, let’s check if (arr[i] + arr[leftSum] + arr[rightSum] = = Sum).
    arr[0] + arr[2] + arr[8] = 11 + 44 + 85 = 140.
    140 > Sum(136) 
    So, decrement rightSum by 1.
dry run
  • Now, let’s check if (arr[i] + arr[leftSum] + arr[rightSum] = = Sum).
    arr[0] + arr[2] + arr[7] = 11 + 44 + 81 = 136.
    136 = Sum(136) 
    So, return true.
     
  • We found a triplet(11, 44, 81) which equals the given sum in the BST.
     

We hope you understand the approach. Now, it's time to code this.

Implementation 

Following is the implementation of this approach in Java.

Java

import java.util.*;

class TripletSum {
    static class BTNode {
        int data;
        BTNode leftChild, rightChild;
    }

    static BTNode newBTNode(int item) {
        BTNode tempBTNode = new BTNode();
        tempBTNode.data = item;
        tempBTNode.leftChild = tempBTNode.rightChild = null;
        return tempBTNode;
    }

    static BTNode insert(BTNode node, int data) {

        if (node == null)
            return newBTNode(data);

        if (data < node.data)
            node.leftChild = insert(node.leftChild, data);
        else if (data > node.data)
            node.rightChild = insert(node.rightChild, data);

        return node;
    }

    static void inorderTraversal(BTNode root, Vector < Integer > al) {
        if (root != null) {
            inorderTraversal(root.leftChild, al);
            al.add(root.data);
            inorderTraversal(root.rightChild, al);
        }
    }

    static boolean findTriplet(BTNode root, int sum) {
        Vector < Integer > al = new Vector < > ();
        inorderTraversal(root, al);
        int leftSum, rightSum;

        for (int i = 0; i < al.size() - 2; i++) {
            leftSum = i + 1;
            rightSum = al.size() - 1;
            while (leftSum < rightSum) {
                if (al.get(i) + al.get(leftSum) + al.get(rightSum) == sum) {
                    return true;
                } else if (al.get(i) + al.get(leftSum) + al.get(rightSum) < sum) {
                    leftSum++;
                } else
                    rightSum--;
            }
        }
        return false;
    }

    public static void main(String[] args) {

        BTNode root = insert(null, 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);

        int sum = 136;

        if (findTriplet(root, sum))
            System.out.print("YES, Triplet Sum EXISTS!");
        else
            System.out.print("NO, Triplet Sum does NOT EXIST!");
    }
}

Output

output


The C++ implementation to check if a triplet with the given sum exists in BST is as follows:

C++

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

struct Node {
    int data;
    struct Node * leftChild, * rightChild;
};

struct Node * newNode(int item) {
    Node * temp = new Node;
    temp -> data = item;
    temp -> leftChild = temp -> rightChild = NULL;
    return temp;
}

void inorder(Node * root, vector < int > & vect) {
    if (root != NULL) {
        inorder(root -> leftChild, vect);
        vect.push_back(root -> data);
        inorder(root -> rightChild, vect);
    }
}

struct Node * insert(Node * 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 -> data)
        node -> leftChild = insert(node -> leftChild, data);
    else if (data > node -> data)
        node -> rightChild = insert(node -> rightChild, data);

    // return the (unchanged) node pointer 
    return node;
}

bool findTriplet(Node * root, int sum) {
    vector < int > vect;
    inorder(root, vect);
    int leftSum, rightSum;

    for (int i = 0; i < vect.size() - 2; i++) {

        leftSum = i + 1;
        rightSum = vect.size() - 1;
        while (leftSum < rightSum) {
            if (vect[i] + vect[leftSum] + vect[rightSum] == sum) {
                return true;
            } 
            else if (vect[i] + vect[leftSum] + vect[rightSum] < sum)
                leftSum++;
            else
                rightSum--;
        }
    }
    return false;
}

int main() {

    struct Node * root = NULL;
    root = insert(root, 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);

    int sum = 135;

    if (findTriplet(root, sum))
        cout << "YES, Triplet Sum EXISTS!";
    else
        cout << "NO, Triplet Sum does not EXIST!";

    return 0;
}
You can also try this code with Online C++ Compiler
Run Code

Output

output

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

output

Let us now discuss the time and space complexity of these codes.

Complexity Analysis

Time Complexity

O(n2is 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.

Check out this problem - Pair Sum In Array.

Approach 2

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:

  1. If the current node is null, return false.
     
  2. 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.
     
  3. If a pair with sum equal to sum minus the current node's value exists, return true. 
     
  4. 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.
     
  5. If no such pair is found, return false.
     

The algorithm for the hasPair function is as follows:

  1. Initialize two stack iterators for traversal of the binary search tree. Create two empty stacks called forward and backward.
     
  2. 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. 
     
  3. 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.
     
  4. 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:

    1. 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.
       
    2. If value1 + value2 == sum, return true.
       
    3. If value1 > value2, break out of the loop because there can be no more pairs with a sum equal to the given sum.
       
    4. 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.
       
    5. 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.
       
  5. 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:

dry run

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.
dry run
  • 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 stackValue2 will be initialized with the data value of the node, which is at the top of the backward stack.
dry run
  • 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.
dry run
  • Now, we’ll pop the top node from the forward stack.
dry run
  • 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:
dry run
  • 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.
dry run
  • 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

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
Run Code

Output

output

Python

# 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

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. 

For placement preparations, you must look at the problemsinterview experiences, and interview bundles. Enrol in our courses and refer to the mock tests and problems available; look at the Problem Sheets, interview experiences, and interview bundle for placement preparations. You can also book an interview session with us.

Consider our paid courses, however, to give your career a competitive advantage!

Happy Coding!

Live masterclass