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.

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

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.
      1. If (head->data + tail-> data < sum) then head = head->right.
      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)
      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(n2)
Space Complexity: O(logn)