Dados dos árboles de búsqueda binarios ( BST ) y un valor X , el problema es imprimir todos los pares de ambos BST cuya suma sea mayor que el valor X dado .
Ejemplos:
Input:
BST 1:
5
/ \
3 7
/ \ / \
2 4 6 8
BST 2:
10
/ \
6 15
/ \ / \
3 8 11 18
X = 20
Output: The pairs are:
(3, 18)
(4, 18)
(5, 18)
(6, 18)
(7, 18)
(8, 18)
(6, 15)
(7, 15)
(8, 15)
Enfoque ingenuo: para cada valor de Node A en BST 1, busque el valor en BST 2 que sea mayor que (X – A). Si se encuentra el valor, imprima el par.
Complejidad de tiempo: O(n1 * h2) , donde n1 es el número de Nodes en el primer BST y h2 es la altura del segundo BST.
Enfoque eficiente:
- Atraviese BST 1 desde el valor más pequeño al Node y al más grande tomando el índice i. Esto se puede lograr con la ayuda de inorder transversal .
- Atraviese BST 2 desde el Node de mayor valor al más pequeño tomando el índice j. Esto se puede lograr con la ayuda del recorrido en orden.
- Realice estos dos recorridos uno por uno y almacene en dos arrays.
- Sume el valor del Node correspondiente de ambos BST en una instancia particular de recorridos.
- Si la suma > x, imprima el par y disminuya j en 1.
- Si x > suma, entonces incrementa i en 1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to print pairs
// from two BSTs whose sum is greater
// the given value x
#include <bits/stdc++.h>
using namespace std;
// Structure of each node of BST
struct node {
int key;
struct node *left, *right;
};
// Function to create a new BST node
node* newNode(int item)
{
node* temp = new node();
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
// A utility function to insert a
// new node with given key in BST
struct node* insert(struct node* node,
int key)
{
// If the tree is empty, return a new node
if (node == NULL)
return newNode(key);
// Otherwise, recur down the tree
if (key < node->key)
node->left = insert(node->left,
key);
else if (key > node->key)
node->right = insert(node->right,
key);
// Return the (unchanged) node pointer
return node;
}
// Function to return the size of
// the tree
int sizeOfTree(node* root)
{
if (root == NULL) {
return 0;
}
// Calculate left size recursively
int left = sizeOfTree(root->left);
// Calculate right size recursively
int right = sizeOfTree(root->right);
// Return total size recursively
return (left + right + 1);
}
// Function to store inorder
// traversal of BST
void storeInorder(node* root,
int inOrder[],
int& index)
{
// Base condition
if (root == NULL) {
return;
}
// Left recursive call
storeInorder(root->left,
inOrder,
index);
// Store elements in inorder array
inOrder[index++] = root->key;
// Right recursive call
storeInorder(root->right,
inOrder,
index);
}
// Function to print the pairs
void print(int inOrder1[], int i,
int index1, int value)
{
while (i < index1) {
cout << "(" << inOrder1[i]
<< ", " << value
<< ")" << endl;
i++;
}
}
// Utility function to check the
// pair of BSTs whose sum is
// greater than given value x
void printPairUtil(int inOrder1[],
int inOrder2[],
int index1,
int j, int k)
{
int i = 0;
while (i < index1 && j >= 0) {
if (inOrder1[i] + inOrder2[j] > k) {
print(inOrder1, i,
index1, inOrder2[j]);
j--;
}
else {
i++;
}
}
}
// Function to check the
// pair of BSTs whose sum is
// greater than given value x
void printPairs(node* root1,
node* root2, int k)
{
// Store the size of BST1
int numNode = sizeOfTree(root1);
// Take auxiliary array for storing
// The inorder traversal of BST1
int inOrder1[numNode + 1];
int index1 = 0;
// Store the size of BST2
numNode = sizeOfTree(root2);
// Take auxiliary array for storing
// The inorder traversal of BST2
int inOrder2[numNode + 1];
int index2 = 0;
// Function call for storing
// inorder traversal of BST1
storeInorder(root1, inOrder1,
index1);
// Function call for storing
// inorder traversal of BST1
storeInorder(root2, inOrder2,
index2);
// Utility function call to count
// the pair
printPairUtil(inOrder1, inOrder2,
index1, index2 - 1, k);
}
// Driver code
int main()
{
/* Formation of BST 1
5
/ \
3 7
/ \ / \
2 4 6 8
*/
struct node* root1 = NULL;
root1 = insert(root1, 5);
insert(root1, 3);
insert(root1, 2);
insert(root1, 4);
insert(root1, 7);
insert(root1, 6);
insert(root1, 8);
/* Formation of BST 2
10
/ \
6 15
/ \ / \
3 8 11 18
*/
struct node* root2 = NULL;
root2 = insert(root2, 10);
insert(root2, 6);
insert(root2, 15);
insert(root2, 3);
insert(root2, 8);
insert(root2, 11);
insert(root2, 18);
int x = 20;
// Print pairs
printPairs(root1, root2, x);
return 0;
}
Java
// Java implementation to print pairs
// from two BSTs whose sum is greater
// the given value x
class GFG{
static class RefInteger
{
Integer value;
public RefInteger(Integer value)
{
this.value = value;
}
}
// Structure of each Node of BST
static class Node
{
int key;
Node left, right;
};
// Function to create a new BST Node
static Node newNode(int item)
{
Node temp = new Node();
temp.key = item;
temp.left = temp.right = null;
return temp;
}
// A utility function to insert a
// new Node with given key in BST
static Node insert(Node Node, int key)
{
// If the tree is empty,
// return a new Node
if (Node == null)
return newNode(key);
// Otherwise, recur down the tree
if (key < Node.key)
Node.left = insert(Node.left, key);
else if (key > Node.key)
Node.right = insert(Node.right, key);
// Return the (unchanged) Node pointer
return Node;
}
// Function to return the size of
// the tree
static int sizeOfTree(Node root)
{
if (root == null)
{
return 0;
}
// Calculate left size recursively
int left = sizeOfTree(root.left);
// Calculate right size recursively
int right = sizeOfTree(root.right);
// Return total size recursively
return (left + right + 1);
}
// Function to store inorder
// traversal of BST
static void storeInorder(Node root, int inOrder[],
RefInteger index)
{
// Base condition
if (root == null)
{
return;
}
// Left recursive call
storeInorder(root.left, inOrder, index);
// Store elements in inorder array
inOrder[index.value++] = root.key;
// Right recursive call
storeInorder(root.right, inOrder, index);
}
// Function to print the pairs
static void print(int inOrder1[], int i,
int index1, int value)
{
while (i < index1)
{
System.out.println("(" + inOrder1[i] +
", " + value + ")");
i++;
}
}
// Utility function to check the
// pair of BSTs whose sum is
// greater than given value x
static void printPairUtil(int inOrder1[],
int inOrder2[],
int index1, int j,
int k)
{
int i = 0;
while (i < index1 && j >= 0)
{
if (inOrder1[i] + inOrder2[j] > k)
{
print(inOrder1, i, index1,
inOrder2[j]);
j--;
}
else
{
i++;
}
}
}
// Function to check the pair of
// BSTs whose sum is greater than
// given value x
static void printPairs(Node root1,
Node root2, int k)
{
// Store the size of BST1
int numNode = sizeOfTree(root1);
// Take auxiliary array for storing
// The inorder traversal of BST1
int[] inOrder1 = new int[numNode + 1];
RefInteger index1 = new RefInteger(0);
// Store the size of BST2
numNode = sizeOfTree(root2);
// Take auxiliary array for storing
// The inorder traversal of BST2
int[] inOrder2 = new int[numNode + 1];
RefInteger index2 = new RefInteger(0);
// Function call for storing
// inorder traversal of BST1
storeInorder(root1, inOrder1, index1);
// Function call for storing
// inorder traversal of BST1
storeInorder(root2, inOrder2, index2);
// Utility function call to count
// the pair
printPairUtil(inOrder1, inOrder2,
index1.value,
index2.value - 1, k);
}
// Driver code
public static void main(String[] args)
{
/* Formation of BST 1
5
/ \
3 7
/ \ / \
2 4 6 8
*/
Node root1 = null;
root1 = insert(root1, 5);
insert(root1, 3);
insert(root1, 2);
insert(root1, 4);
insert(root1, 7);
insert(root1, 6);
insert(root1, 8);
/* Formation of BST 2
10
/ \
6 15
/ \ / \
3 8 11 18
*/
Node root2 = null;
root2 = insert(root2, 10);
insert(root2, 6);
insert(root2, 15);
insert(root2, 3);
insert(root2, 8);
insert(root2, 11);
insert(root2, 18);
int x = 20;
// Print pairs
printPairs(root1, root2, x);
}
}
// This code is contributed by sanjeev2552
Python3
# Python3 implementation to print pairs
# from two BSTs whose sum is greater
# the given value x
index = 0
# Structure of each node of BST
class newNode:
def __init__(self, item):
self.key = item
self.left = None
self.right = None
# A utility function to insert a
# new node with given key in BST
def insert(node, key):
# If the tree is empty,
# return a new node
if (node == None):
return newNode(key)
# Otherwise, recur down the tree
if (key < node.key):
node.left = insert(node.left, key)
elif (key > node.key):
node.right = insert(node.right, key)
# Return the (unchanged) node pointer
return node
# Function to return the size of
# the tree
def sizeOfTree(root):
if (root == None):
return 0
# Calculate left size recursively
left = sizeOfTree(root.left)
# Calculate right size recursively
right = sizeOfTree(root.right)
# Return total size recursively
return (left + right + 1)
# Function to store inorder
# traversal of BST
def storeInorder(root, inOrder):
global index
# Base condition
if (root == None):
return
# Left recursive call
storeInorder(root.left, inOrder)
# Store elements in inorder array
inOrder[index] = root.key
index += 1
# Right recursive call
storeInorder(root.right, inOrder)
# Function to print the pairs
def print1(inOrder1, i, index1, value):
while (i < index1):
print("(", inOrder1[i], ",", value, ")")
i += 1
# Utility function to check the
# pair of BSTs whose sum is
# greater than given value x
def printPairUtil(inOrder1, inOrder2,
index1, j, k):
i = 0
while (i < index1 and j >= 0):
if (inOrder1[i] + inOrder2[j] > k):
print1(inOrder1, i, index1, inOrder2[j])
j -= 1
else:
i += 1
# Function to check the
# pair of BSTs whose sum is
# greater than given value x
def printPairs(root1, root2, k):
global index
# Store the size of BST1
numNode = sizeOfTree(root1)
# Take auxiliary array for storing
# The inorder traversal of BST1
inOrder1 = [0 for i in range(numNode + 1)]
index1 = 0
# Store the size of BST2
numNode = sizeOfTree(root2)
# Take auxiliary array for storing
# The inorder traversal of BST2
inOrder2 = [0 for i in range(numNode + 1)]
index2 = 0
# Function call for storing
# inorder traversal of BST1
index = 0
storeInorder(root1, inOrder1)
temp1 = index
# Function call for storing
# inorder traversal of BST1
index = 0
storeInorder(root2, inOrder2)
temp2 = index
# Utility function call to count
# the pair
printPairUtil(inOrder1, inOrder2,
temp1, temp2 - 1, k)
# Driver code
if __name__ == '__main__':
''' Formation of BST 1
5
/ \
3 7
/ \ / \
2 4 6 8
'''
root1 = None
root1 = insert(root1, 5)
insert(root1, 3)
insert(root1, 2)
insert(root1, 4)
insert(root1, 7)
insert(root1, 6)
insert(root1, 8)
'''Formation of BST 2
10
/ \
6 15
/ \ / \
3 8 11 18
'''
root2 = None
root2 = insert(root2, 10)
insert(root2, 6)
insert(root2, 15)
insert(root2, 3)
insert(root2, 8)
insert(root2, 11)
insert(root2, 18)
x = 20
# Print pairs
printPairs(root1, root2, x)
# This code is contributed by ipg2016107
C#
// C# implementation to print pairs
// from two BSTs whose sum is greater
// the given value x
using System;
class GFG{
public class Refint
{
public int value;
public Refint(int value)
{
this.value = value;
}
}
// Structure of each Node of BST
public class Node
{
public int key;
public Node left, right;
};
// Function to create a new BST Node
static Node newNode(int item)
{
Node temp = new Node();
temp.key = item;
temp.left = temp.right = null;
return temp;
}
// A utility function to insert a
// new Node with given key in BST
static Node insert(Node Node, int key)
{
// If the tree is empty,
// return a new Node
if (Node == null)
return newNode(key);
// Otherwise, recur down the tree
if (key < Node.key)
Node.left = insert(Node.left, key);
else if (key > Node.key)
Node.right = insert(Node.right, key);
// Return the (unchanged) Node pointer
return Node;
}
// Function to return the size of
// the tree
static int sizeOfTree(Node root)
{
if (root == null)
{
return 0;
}
// Calculate left size recursively
int left = sizeOfTree(root.left);
// Calculate right size recursively
int right = sizeOfTree(root.right);
// Return total size recursively
return (left + right + 1);
}
// Function to store inorder
// traversal of BST
static void storeInorder(Node root, int []inOrder,
Refint index)
{
// Base condition
if (root == null)
{
return;
}
// Left recursive call
storeInorder(root.left, inOrder, index);
// Store elements in inorder array
inOrder[index.value++] = root.key;
// Right recursive call
storeInorder(root.right, inOrder, index);
}
// Function to print the pairs
static void print(int []inOrder1, int i,
int index1, int value)
{
while (i < index1)
{
Console.WriteLine("(" + inOrder1[i] +
", " + value + ")");
i++;
}
}
// Utility function to check the
// pair of BSTs whose sum is
// greater than given value x
static void printPairUtil(int []inOrder1,
int []inOrder2,
int index1, int j,
int k)
{
int i = 0;
while (i < index1 && j >= 0)
{
if (inOrder1[i] + inOrder2[j] > k)
{
print(inOrder1, i, index1,
inOrder2[j]);
j--;
}
else
{
i++;
}
}
}
// Function to check the pair of
// BSTs whose sum is greater than
// given value x
static void printPairs(Node root1,
Node root2, int k)
{
// Store the size of BST1
int numNode = sizeOfTree(root1);
// Take auxiliary array for storing
// The inorder traversal of BST1
int[] inOrder1 = new int[numNode + 1];
Refint index1 = new Refint(0);
// Store the size of BST2
numNode = sizeOfTree(root2);
// Take auxiliary array for storing
// The inorder traversal of BST2
int[] inOrder2 = new int[numNode + 1];
Refint index2 = new Refint(0);
// Function call for storing
// inorder traversal of BST1
storeInorder(root1, inOrder1, index1);
// Function call for storing
// inorder traversal of BST1
storeInorder(root2, inOrder2, index2);
// Utility function call to count
// the pair
printPairUtil(inOrder1, inOrder2,
index1.value,
index2.value - 1, k);
}
// Driver code
public static void Main(string[] args)
{
/* Formation of BST 1
5
/ \
3 7
/ \ / \
2 4 6 8
*/
Node root1 = null;
root1 = insert(root1, 5);
insert(root1, 3);
insert(root1, 2);
insert(root1, 4);
insert(root1, 7);
insert(root1, 6);
insert(root1, 8);
/* Formation of BST 2
10
/ \
6 15
/ \ / \
3 8 11 18
*/
Node root2 = null;
root2 = insert(root2, 10);
insert(root2, 6);
insert(root2, 15);
insert(root2, 3);
insert(root2, 8);
insert(root2, 11);
insert(root2, 18);
int x = 20;
// Print pairs
printPairs(root1, root2, x);
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// JavaScript implementation to print pairs
// from two BSTs whose sum is greater
// the given value x
class Refint
{
constructor(value)
{
this.value = value;
}
}
// Structure of each Node of BST
class Node
{
constructor(item) {
this.left = null;
this.right = null;
this.key = item;
}
}
// Function to create a new BST Node
function newNode(item)
{
let temp = new Node(item);
return temp;
}
// A utility function to insert a
// new Node with given key in BST
function insert(Node, key)
{
// If the tree is empty,
// return a new Node
if (Node == null)
return newNode(key);
// Otherwise, recur down the tree
if (key < Node.key)
Node.left = insert(Node.left, key);
else if (key > Node.key)
Node.right = insert(Node.right, key);
// Return the (unchanged) Node pointer
return Node;
}
// Function to return the size of
// the tree
function sizeOfTree(root)
{
if (root == null)
{
return 0;
}
// Calculate left size recursively
let left = sizeOfTree(root.left);
// Calculate right size recursively
let right = sizeOfTree(root.right);
// Return total size recursively
return (left + right + 1);
}
// Function to store inorder
// traversal of BST
function storeInorder(root, inOrder, index)
{
// Base condition
if (root == null)
{
return;
}
// Left recursive call
storeInorder(root.left, inOrder, index);
// Store elements in inorder array
inOrder[index.value++] = root.key;
// Right recursive call
storeInorder(root.right, inOrder, index);
}
// Function to print the pairs
function print(inOrder1, i, index1, value)
{
while (i < index1)
{
document.write("(" + inOrder1[i] +
", " + value + ")" + "</br>");
i++;
}
}
// Utility function to check the
// pair of BSTs whose sum is
// greater than given value x
function printPairUtil(inOrder1, inOrder2, index1, j, k)
{
let i = 0;
while (i < index1 && j >= 0)
{
if (inOrder1[i] + inOrder2[j] > k)
{
print(inOrder1, i, index1,
inOrder2[j]);
j--;
}
else
{
i++;
}
}
}
// Function to check the pair of
// BSTs whose sum is greater than
// given value x
function printPairs(root1, root2, k)
{
// Store the size of BST1
let numNode = sizeOfTree(root1);
// Take auxiliary array for storing
// The inorder traversal of BST1
let inOrder1 = new Array(numNode + 1);
let index1 = new Refint(0);
// Store the size of BST2
numNode = sizeOfTree(root2);
// Take auxiliary array for storing
// The inorder traversal of BST2
let inOrder2 = new Array(numNode + 1);
let index2 = new Refint(0);
// Function call for storing
// inorder traversal of BST1
storeInorder(root1, inOrder1, index1);
// Function call for storing
// inorder traversal of BST1
storeInorder(root2, inOrder2, index2);
// Utility function call to count
// the pair
printPairUtil(inOrder1, inOrder2,
index1.value,
index2.value - 1, k);
}
/* Formation of BST 1
5
/ \
3 7
/ \ / \
2 4 6 8
*/
let root1 = null;
root1 = insert(root1, 5);
insert(root1, 3);
insert(root1, 2);
insert(root1, 4);
insert(root1, 7);
insert(root1, 6);
insert(root1, 8);
/* Formation of BST 2
10
/ \
6 15
/ \ / \
3 8 11 18
*/
let root2 = null;
root2 = insert(root2, 10);
insert(root2, 6);
insert(root2, 15);
insert(root2, 3);
insert(root2, 8);
insert(root2, 11);
insert(root2, 18);
let x = 20;
// Print pairs
printPairs(root1, root2, x);
</script>
Producción:
(3, 18) (4, 18) (5, 18) (6, 18) (7, 18) (8, 18) (6, 15) (7, 15) (8, 15)
Publicación traducida automáticamente
Artículo escrito por MohammadMudassir y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA