Найти, есть ли триплет в сбалансированном BST, который добавляет к нулю

// Программа на C ++, чтобы проверить, есть ли
// триплет с суммой, равной 0 в
// данный BST
#include <bits/stdc++.h>

using namespace std;

  
// BST узел имеет ключ, а также левый и правый указатели

class node 

{ 

    public:

    int key; 

    node *left; 

    node *right; 

}; 

  
// Функция для преобразования данного BST в Doubly
// Связанный список. левый указатель используется
// как предыдущий указатель и правый указатель
// используется в качестве следующего указателя. Функция
// устанавливает * голову, чтобы указать на первый и * хвост
// чтобы указать на последний узел преобразованной DLL

void convertBSTtoDLL(node* root, node** head, node** tail) 

{ 

    // Базовый вариант

    if (root == NULL) 

        return; 

    // Сначала конвертируем левое поддерево

    if (root->left) 

        convertBSTtoDLL(root->left, head, tail); 

    // Затем меняем левый угол текущего корня

    // как последний узел левого поддерева

    root->left = *tail; 

    // Если tail не равен NULL, тогда устанавливается правильно

    // хвоста как корень, иначе текущий

    // узел - голова

    if (*tail) 

        (*tail)->right = root; 

    else

        *head = root; 

    // Обновление хвоста

    *tail = root; 

    // Наконец, преобразовать правильное поддерево

    if (root->right) 

        convertBSTtoDLL(root->right, head, tail); 

} 

  
// Эта функция возвращает true, если есть
// пара в DLL с суммой, равной заданному
// сумма Алгоритм похож на hasArrayTwoCandidates ()
// в методе 1 http://tinyurl.com/dy6palr

bool 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; 

} 

  
// Основная функция, которая возвращает
// истина, если в триплете с 0 суммой
// BST в противном случае возвращает false

bool isTripletPresent(node *root) 

{ 

    // Проверяем, является ли данный BST пустым

    if (root == NULL) 

    return false; 

    // Преобразовать данный BST в двусвязный список. голова и хвост хранят

    // указатели на первый и последний узлы в DLLL

    node* head = NULL; 

    node* tail = NULL; 

    convertBSTtoDLL(root, &head, &tail); 

    // Теперь перебираем все узлы и

    // найти, есть ли пара с суммой

    // равно -1 * heaf-> key, где head это текущий узел

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

    { 

        // Если есть пара с суммой

        // равно -1 * head-> key, затем возвращаем

        // правда еще двигаться вперед

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

            return true; 

        else

            head = head->right; 

    } 

    // Если мы достигнем здесь, то

    // триплета с нулевой суммой не было

    return false; 

} 

  
// Полезная функция для создания
// новый узел BST с ключом с заданным номером

node* newNode(int num) 

{ 

    node* temp = new node(); 

    temp->key = num; 

    temp->left = temp->right = NULL; 

    return temp; 

} 

  
// Утилита для вставки заданного ключа в BST

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; 

} 

  
// Код драйвера

int main() 

{ 

    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)) 

        cout << "Present"; 

    else

        cout << "Not Present"; 

    return 0; 

} 

  
// Этот код предоставлен rathbhupendra

// Программа AC для проверки наличия триплета с суммой, равной 0 в
// данный BST
#include<stdio.h>

  
// BST узел имеет ключ, а также левый и правый указатели

struct node

{

    int key;

    struct node *left;

    struct node *right;

};

  
// Функция для преобразования данного BST в двусвязный список. левый указатель используется
// как предыдущий указатель, а правый указатель используется как следующий указатель. Функция
// устанавливает * head для указания на первый и * tail для указания на последний узел преобразованной DLL

void convertBSTtoDLL(node* root, node** head, node** tail)

{

    // Базовый вариант

    if (root == NULL)

        return;

    // Сначала конвертируем левое поддерево

    if (root->left)

        convertBSTtoDLL(root->left, head, tail);

    // Затем меняем левый угол текущего корня на последний узел левого поддерева

    root->left = *tail;

    // Если tail не равен NULL, тогда установить права на tail как root, иначе текущий

    // узел - голова

    if (*tail)

        (*tail)->right = root;

    else

        *head = root;

    // Обновление хвоста

    *tail = root;

    // Наконец, преобразовать правильное поддерево

    if (root->right)

        convertBSTtoDLL(root->right, head, tail);

}

  
// Эта функция возвращает true, если в DLL есть пара с равной суммой
// до заданной суммы. Алгоритм похож на hasArrayTwoCandidates ()
// в методе 1 http://tinyurl.com/dy6palr

bool 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;

}

  
// Основная функция, которая возвращает true, если в триплете с 0 суммой
// BST в противном случае возвращает false

bool isTripletPresent(node *root)

{

    // Проверяем, является ли данный BST пустым

    if (root == NULL)

       return false;

    // Преобразовать данный BST в двусвязный список. голова и хвост хранят

    // указатели на первый и последний узлы в DLLL

    node* head = NULL;

    node* tail = NULL;

    convertBSTtoDLL(root, &head, &tail);

    // Теперь итерация по каждому узлу и поиск пары с суммой

    // равно -1 * heaf-> key, где head это текущий узел

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

    {

        // Если есть пара с суммой, равной -1 * head-> key, возвращаем

        // правда еще двигаться вперед

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

            return true;

        else

            head = head->right;

    }

    // Если мы доберемся сюда, то триплета с нулевой суммой не было

    return false;

}

  
// Вспомогательная функция для создания нового узла BST с ключом с заданным номером

node* newNode(int num)

{

    node* temp = new node;

    temp->key = num;

    temp->left = temp->right = NULL;

    return temp;

}

  
// Утилита для вставки заданного ключа в BST

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;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    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))

        printf("Present");

    else

        printf("Not Present");

    return 0;

}