# Triplets in a Binary Search Tree that sum to zero

By | February 23, 2016

# Triplets in a Binary Search Tree that sum to zero.

### Problem statement to find three numbers in a binary search tree that sum to zero:

Given a balanced binary search tree (BST), determine if there exist three numbers that add up to zero.If they exist, output YES.

### Example for testing if 3 numbers in a BST add up to zero:

```INPUT:
2
/     \
-5      5
/  \    /  \
-9   -3  4   11
OUTPUT: YES
The output is YES, because the triplet (-9, 5 ,4 ) sums to zero.```

### Method 1: Brute Force (naive) approach using an auxiliary array:-

1. Create an array from inorder traversal of the binary search tree (BST) .
2. Now the question is reduced to Find a Triplet in the Given Array that sums to a Given Value (with value = 0).

Time Complexity: O(n2)/O(n3(see the above linked post for explanation)
Auxiliary Space: O(n)

### Method 2:Using Doubly Linked Lists.

Create a doubly linked list from the given binary search tree. It takes up logn extra space. This is so because while creating a doubly inked list (DLL), the maximum number of nodes that may be pushed into the stack of creating a DLL is equal to the height of the tree (height of a binary search tree with n nodes is logn).
Then follow the algorithm on DLL to test the presence of a triplet.

### Algorithm for checking if the Binary Search Tree (BST) has three numbers whose resultant sum is zero:

1. Convert the given binary search tree to a doubly linked list.
2. Traverse the entire list and compare the sum of other two elements with this current node.
3. Initialize a variable ‘sum’ as -1 * (current->data).
1. Loop while head != tail.
2. Else if(head->data + tail-> data > sum) then tail = tail->left.
3. Else if (head->data + tail-> data == sum) then return true.
4. Repeat the above steps while head->data < 0 and head->right != tail.

#### Solution code in C++ to find Triplets in a Binary Search Tree that sum to zero:

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

/*Structure of each node of tree*/
struct node{
int data;
node *left,*right;
};

/*Function to convert BST to a DLL*/
void BSTtoDLL(node* root, node** head, node** tail)
{
if(!root)
return;

/*DLL from left subtree*/
if(root->left)

/*Change left of the current root as last
node of left subtree*/
root->left = *tail;

/*If tail is not NULL, then set the right
of tail as root, else current node is head*/
if (*tail)
(*tail)->right = root;
else

/*Modify the tail*/
*tail = root;

/*Convert the right subtree*/
if (root->right)
}

/*This function returns true if there exists a pair
whose sum is equal to the current element*/
bool isPairPresent(node* head, node* tail, int sum)
{
/*Checks the DLL for such a pair*/
{
int current = head->data + tail->data;
if(current == sum)
return sum;

else if(current < sum)

else
tail = tail->left;
}
return false;
}

/*This function checks if a triplet adding up to
zero exists or not*/
bool isTripletPresent(node* root)
{
if(!root)
return false;

/*Convert BST to DLL and assign head and tail
pointers to first and last node resp*/
node* tail = NULL;

/*Traverse the entire BST and find a pair with
sum = -1*(current node's key)*/
{
return true;

else
}

/*If no triplet was found*/
return false;
}

/*This function creates and
initialises new nodes*/
node * newNode(int data)
{
node* temp = new node;
temp->data=data;
temp->right=temp->left=NULL;
return temp;
}

/*This function inserts new nodes
int the Binary Search Tree*/
node * Insert(node * root, int data)
{
if(!root)
return newNode(data);

if(data<root->data)
root->left=Insert(root->left,data);
else
root->right=Insert(root->right,data);

return root;
}

/* Driver Program to test above functions */
int main()
{
/* The following insertions create this
Binary Search Tree
2
/     \
-5      5
/  \    /  \
-9   -3  4   11 */

node *root = NULL;
root = Insert(root, 2);
Insert(root, -5);
Insert(root, 5);
Insert(root, -9);
Insert(root, -3);
Insert(root, 4);
Insert(root, 11);

if(isTripletPresent(root))
cout<<"The triplet exists";
else
cout<<"Such a triplet is not present";

return 0;
}```

### Output:

`The triplet exists.`

Time Complexity: O(n2)
Space Complexity: O(logn)