Triplet with 0 sum in BST Java

PROGRAM TO IF THERE IS A TRIPLET IN A BALANCED BST THAT ADDS TO ZERO

import java.util.*;

class MAIN

{

 

  // A BST node has key, and left and right pointers

  static class node

  {

    int key;

    node left;

    node right;

  };

  static node head;

  static node tail;

 

  // A function to convert given BST to Doubly

  // Linked List. left pointer is used

  // as previous pointer and right pointer

  // is used as next pointer. The function

  // sets *head to point to first and *tail

  // to point to last node of converted DLL

  static void convertBSTtoDLL(node root)

  {

 

    // Base case

    if (root == null)

      return;

 

    // First convert the left subtree

    if (root.left != null)

      convertBSTtoDLL(root.left);

 

    // Then change left of current root

    // as last node of left subtree

    root.left = tail;

 

    // If tail is not null, then set right

    // of tail as root, else current

    // node is head

    if (tail != null)

      (tail).right = root;

    else

      head = root;

 

    // Update tail

    tail = root;

 

    // Finally, convert right subtree

    if (root.right != null)

      convertBSTtoDLL(root.right);

  }

 

  // This function returns true if there

  // is pair in DLL with sum equal to given

  // sum. The algorithm is similar to hasArrayTwoCandidates()

  // in method 1 of http://tinyurl.com/dy6palr

  static boolean isPresentInDLL(node head, node tail, int sum)

  {

    while (head != tail)

    {

      int curr = head.key + tail.key;

      if (curr == sum)

        return true;

      else if (curr > sum)

        tail = tail.left;

      else

        head = head.right;

    }

    return false;

  }

 

  // The main function that returns

  // true if there is a 0 sum triplet in

  // BST otherwise returns false

  static boolean isTripletPresent(node root)

  {

    // Check if the given BST is empty

    if (root == null)

      return false;

 

    // Convert given BST to doubly linked list. head and tail store the

    // pointers to first and last nodes in DLLL

    head = null;

    tail = null;

    convertBSTtoDLL(root);

 

    // Now iterate through every node and

    // find if there is a pair with sum

    // equal to -1 * heaf.key where head is current node

    while ((head.right != tail) && (head.key < 0))

    {

      // If there is a pair with sum

      // equal to -1*head.key, then return

      // true else move forward

      if (isPresentInDLL(head.right, tail, -1*head.key))

        return true;

      else

        head = head.right;

    }

 

    // If we reach here, then

    // there was no 0 sum triplet

    return false;

  }

 

  // A utility function to create

  // a new BST node with key as given num

  static node newNode(int num)

  {

    node temp = new node();

    temp.key = num;

    temp.left = temp.right = null;

    return temp;

  }

 

  // A utility function to insert a given key to BST

  static node insert(node root, int key)

  {

    if (root == null)

      return newNode(key);

    if (root.key > key)

      root.left = insert(root.left, key);

    else

      root.right = insert(root.right, key);

    return root;

  }

 

  // Driver code

  public static void main(String[] args)

  {

    node root = null;

    root = insert(root, 6);

    root = insert(root, -13);

    root = insert(root, 14);

    root = insert(root, -8);

    root = insert(root, 15);

    root = insert(root, 13);

    root = insert(root, 7);

    if (isTripletPresent(root))

      System.out.print("Present");

    else

      System.out.print("Not Present");

  }

}

OUTPUT:

Present

CREDITS: https://www.geeksforgeeks.org/find-if-there-is-a-triplet-in-bst-that-adds-to-0/