# 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 / \ -55/ \ / \-9-3411OUTPUT:YES The output is YES, because the triplet (-9, 5 ,4 ) sums to zero.

### Triplets in a Binary Search Tree that sum to zero Solution:

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

- Create an array from inorder traversal of the binary search tree (BST) .
- 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(n ^{2})/O(n^{3}) **(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:

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

- Loop while head != tail.
- 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) BSTtoDLL(root->left, head, tail); /*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 *head = root; /*Modify the tail*/ *tail = root; /*Convert the right subtree*/ if (root->right) BSTtoDLL(root->right, head, tail); } /*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*/ while(head != tail) { int current = head->data + tail->data; if(current == sum) return sum; else if(current < sum) head=head->right; 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* head = NULL; node* tail = NULL; BSTtoDLL(root, &head, &tail); /*Traverse the entire BST and find a pair with sum = -1*(current node's key)*/ while((head->right != tail) && (head->data < 0)) { if(isPairPresent(head->right, tail,-1*head->data)) return true; else head = head->right; } /*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(n ^{2})**

Space Complexity:

**O(logn)**