Dado un árbol de búsqueda binario y un entero X , la tarea es encontrar si existe un triplete con suma X. Escriba Sí o No según corresponda. Tenga en cuenta que los tres Nodes pueden no ser necesariamente distintos.
Ejemplos:
Input: X = 15
5
/ \
3 7
/ \ / \
2 4 6 8
Output: Yes
{5, 5, 5} is one such triplet.
{3, 5, 7}, {2, 5, 8}, {4, 5, 6} are some others.
Input: X = 16
1
\
2
\
3
\
4
\
5
Output: No
Enfoque simple: un enfoque simple será convertir el BST en una array ordenada y luego encontrar el triplete usando punteros de tres puntos. Esto ocupará O(N) espacio extra donde N es el número de Nodes presentes en el árbol de búsqueda binaria. Ya hemos discutido un problema similar en este artículo que ocupa O (N) espacio adicional.
Mejor enfoque: Resolveremos este problema usando un método eficiente en el espacio al reducir la complejidad del espacio adicional a O(H) donde H es la altura de BST. Para eso, usaremos la técnica de dos punteros en BST.
Recorreremos todos los Nodes del árbol uno por uno y para cada Node, intentaremos encontrar un par con una suma igual a (X – curr->data) donde ‘curr’ es el Node actual del BST que estamos atravesando
Usaremos una técnica similar a la técnica discutida en este artículo para encontrar un par.
Algoritmo: recorrer cada Node de BST uno por uno y para cada Node:
- Cree un iterador hacia adelante y hacia atrás para BST. Digamos que el valor de los Nodes a los que apuntan es v1 y v2.
- Ahora en cada paso,
- Si v1 + v2 = X, encontramos un par, por lo que aumentaremos la cuenta en 1.
- Si v1 + v2 es menor o igual que x, haremos que el iterador hacia adelante apunte al siguiente elemento.
- Si v1 + v2 es mayor que x, haremos que el iterador hacia atrás apunte al elemento anterior.
- Continuaremos con lo anterior mientras el iterador izquierdo no apunte a un Node con un valor mayor que el Node derecho.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Node of the binary tree
struct node {
int data;
node* left;
node* right;
node(int data)
{
this->data = data;
left = NULL;
right = NULL;
}
};
// Function that returns true if a pair exists
// in the binary search tree with sum equal to x
bool existsPair(node* root, int x)
{
// Iterators for BST
stack<node *> it1, it2;
// Initializing forward iterator
node* c = root;
while (c != NULL)
it1.push(c), c = c->left;
// Initializing backward iterator
c = root;
while (c != NULL)
it2.push(c), c = c->right;
// Two pointer technique
while (it1.size() and it2.size()) {
// Variables to store values at
// it1 and it2
int v1 = it1.top()->data, v2 = it2.top()->data;
// Base case
if (v1 + v2 == x)
return 1;
if (v1 > v2)
break;
// Moving forward pointer
if (v1 + v2 < x) {
c = it1.top()->right;
it1.pop();
while (c != NULL)
it1.push(c), c = c->left;
}
// Moving backward pointer
else {
c = it2.top()->left;
it2.pop();
while (c != NULL)
it2.push(c), c = c->right;
}
}
// Case when no pair is found
return 0;
}
// Function that returns true if a triplet exists
// in the binary search tree with sum equal to x
bool existsTriplet(node* root, node* curr, int x)
{
// If current node is NULL
if (curr == NULL)
return 0;
// Conditions for existence of a triplet
return (existsPair(root, x - curr->data)
|| existsTriplet(root, curr->left, x)
|| existsTriplet(root, curr->right, x));
}
// Driver code
int main()
{
node* root = new node(5);
root->left = new node(3);
root->right = new node(7);
root->left->left = new node(2);
root->left->right = new node(4);
root->right->left = new node(6);
root->right->right = new node(8);
int x = 24;
if (existsTriplet(root, root, x))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java implementation of the approach
import java.io.*;
import java.util.*;
// Node of the binary tree
class Node
{
int data;
Node left, right;
Node(int item)
{
data = item;
left = right = null;
}
}
class GFG
{
static Node root;
// Function that returns true if a pair exists
// in the binary search tree with sum equal to x
static boolean existsPair(Node root, int x)
{
// Iterators for BST
Stack<Node> it1 = new Stack<Node>();
Stack<Node> it2 = new Stack<Node>();
// Initializing forward iterator
Node c = root;
while (c != null)
{
it1.push(c);
c = c.left;
}
// Initializing backward iterator
c = root;
while (c != null)
{
it2.push(c);
c = c.right;
}
// Two pointer technique
while (it1.size() > 0 && it2.size() > 0)
{
// Variables to store values at
// it1 and it2
int v1 = it1.peek().data;
int v2 = it2.peek().data;
// Base case
if (v1 + v2 == x)
{
return true;
}
if (v1 > v2)
{
break;
}
// Moving forward pointer
if (v1 + v2 < x)
{
c = it1.peek().right;
it1.pop();
while (c != null)
{
it1.push(c);
c = c.left;
}
}
// Moving backward pointer
else
{
c = it2.peek().left;
it2.pop();
while(c != null)
{
it2.push(c);
c = c.right;
}
}
}
// Case when no pair is found
return false;
}
// Function that returns true if a triplet exists
// in the binary search tree with sum equal to x
static boolean existsTriplet(Node root,
Node curr, int x )
{
// If current node is NULL
if(curr == null)
{
return false;
}
// Conditions for existence of a triplet
return (existsPair(root, x - curr.data) ||
existsTriplet(root, curr.left, x) ||
existsTriplet(root, curr.right, x));
}
// Driver code
public static void main (String[] args)
{
GFG tree = new GFG();
tree.root = new Node(5);
tree.root.left = new Node(3);
tree.root.right = new Node(7);
tree.root.left.left = new Node(2);
tree.root.left.right = new Node(4);
tree.root.right.left = new Node(6);
tree.root.right.right = new Node(8);
int x = 24;
if (existsTriplet(root, root, x))
{
System.out.println("Yes");
}
else
{
System.out.println("No");
}
}
}
// This code is contributed by avanitrachhadiya2155
Python3
# Python3 implementation of the approach
class Node:
def __init__(self, x):
self.data = x
self.left = None
self.right = None
# Function that returns true if a pair exists
# in the binary search tree with sum equal to x
def existsPair(root, x):
# Iterators for BST
it1, it2 = [], []
# Initializing forward iterator
c = root
while (c != None):
it1.append(c)
c = c.left
# Initializing backward iterator
c = root
while (c != None):
it2.append(c)
c = c.right
# Two pointer technique
while (len(it1) > 0 and len(it2) > 0):
# Variables to store values at
# it1 and it2
v1 = it1[-1].data
v2 = it2[-1].data
# Base case
if (v1 + v2 == x):
return 1
if (v1 > v2):
break
# Moving forward pointer
if (v1 + v2 < x):
c = it1[-1].right
del it1[-1]
while (c != None):
it1.append(c)
c = c.left
# Moving backward pointer
else:
c = it2[-1].left
del it2[-1]
while (c != None):
it2.append(c)
c = c.right
# Case when no pair is found
return 0
# Function that returns true if a triplet exists
# in the binary search tree with sum equal to x
def existsTriplet(root, curr, x):
# If current node is NULL
if (curr == None):
return 0
# Conditions for existence of a triplet
return (existsPair(root, x - curr.data)
or existsTriplet(root, curr.left, x)
or existsTriplet(root, curr.right, x))
# Driver code
if __name__ == '__main__':
root = Node(5)
root.left = Node(3)
root.right = Node(7)
root.left.left = Node(2)
root.left.right = Node(4)
root.right.left = Node(6)
root.right.right = Node(8)
x = 24
if (existsTriplet(root, root, x)):
print("Yes")
else:
print("No")
# This code is contributed by mohit kumar 29
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
// Node of the binary tree
class Node
{
public int data;
public Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
class GFG{
static Node root;
// Function that returns true if a pair exists
// in the binary search tree with sum equal to x
static bool existsPair(Node root, int x)
{
// Iterators for BST
Stack<Node> it1 = new Stack<Node>();
Stack<Node> it2 = new Stack<Node>();
// Initializing forward iterator
Node c = root;
while (c != null)
{
it1.Push(c);
c = c.left;
}
// Initializing backward iterator
c = root;
while (c != null)
{
it2.Push(c);
c = c.right;
}
// Two pointer technique
while (it1.Count > 0 && it2.Count > 0)
{
// Variables to store values at
// it1 and it2
int v1 = it1.Peek().data;
int v2 = it2.Peek().data;
// Base case
if (v1 + v2 == x)
{
return true;
}
if (v1 > v2)
{
break;
}
// Moving forward pointer
if (v1 + v2 < x)
{
c = it1.Peek().right;
it1.Pop();
while (c != null)
{
it1.Push(c);
c = c.left;
}
}
// Moving backward pointer
else
{
c = it2.Peek().left;
it2.Pop();
while(c != null)
{
it2.Push(c);
c = c.right;
}
}
}
// Case when no pair is found
return false;
}
// Function that returns true if a triplet exists
// in the binary search tree with sum equal to x
static bool existsTriplet(Node root, Node curr, int x)
{
// If current node is NULL
if (curr == null)
{
return false;
}
// Conditions for existence of a triplet
return (existsPair(root, x - curr.data) ||
existsTriplet(root, curr.left, x) ||
existsTriplet(root, curr.right, x));
}
// Driver code
static public void Main()
{
GFG.root = new Node(5);
GFG.root.left = new Node(3);
GFG.root.right = new Node(7);
GFG.root.left.left = new Node(2);
GFG.root.left.right = new Node(4);
GFG.root.right.left = new Node(6);
GFG.root.right.right = new Node(8);
int x = 24;
if (existsTriplet(root, root, x))
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}
}
}
// This code is contributed by rag2127
Javascript
<script>
// Javascript implementation of the approach
// Node of the binary tree
class node
{
constructor(data)
{
this.data = data;
this.left = this.right = null;
}
}
// Function to find a pair with given sum
function existsPair(root, x)
{
// Iterators for BST
let it1 = [], it2 = [];
// Initializing forward iterator
let c = root;
while (c != null)
{
it1.push(c);
c = c.left;
}
// Initializing backward iterator
c = root;
while (c != null)
{
it2.push(c);
c = c.right;
}
// Two pointer technique
while (it1.length > 0 && it2.length > 0)
{
// Variables to store values at
// it1 and it2
let v1 = it1[it1.length - 1].data,
v2 = it2[it2.length - 1].data;
// Base case
if (v1 + v2 == x)
return true;
if (v1 > v2)
{
break;
}
// Moving forward pointer
if (v1 + v2 < x)
{
c = it1[it1.length - 1].right;
it1.pop();
while (c != null)
{
it1.push(c);
c = c.left;
}
}
// Moving backward pointer
else
{
c = it2[it2.length - 1].left;
it2.pop();
while (c != null)
{
it2.push(c);
c = c.right;
}
}
}
// Case when no pair is found
return false;
}
// Function that returns true if a
// triplet exists in the binary
// search tree with sum equal to x
function existsTriplet(root, curr, x)
{
// If current node is NULL
if (curr == null)
{
return false;
}
// Conditions for existence of a triplet
return (existsPair(root, x - curr.data) ||
existsTriplet(root, curr.left, x) ||
existsTriplet(root, curr.right, x));
}
// Driver code
let root = new node(5);
root.left = new node(3);
root.right = new node(7);
root.left.left = new node(2);
root.left.right = new node(4);
root.right.left = new node(6);
root.right.right = new node(8);
let x = 24;
// Calling required function
if (existsTriplet(root, root, x))
document.write("Yes");
else
document.write("No");
// This code is contributed by unknown2108
</script>
Producción:
Yes
Complejidad temporal: O(N 2 )
Complejidad espacial: O(H), ya que se ha tomado H espacio extra.
Publicación traducida automáticamente
Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA