Dados dos árboles de búsqueda binarios que consisten en elementos positivos únicos, debemos verificar si los dos BST contienen el mismo conjunto de elementos o no.
Nota : La estructura de los dos BST dados puede ser diferente.
C++
// CPP program to check if two BSTs contains
// same set of elements
#include<bits/stdc++.h>
using namespace std;
// BST Node
struct Node
{
int data;
struct Node* left;
struct Node* right;
};
// Utility function to create new Node
Node* newNode(int val)
{
Node* temp = new Node;
temp->data = val;
temp->left = temp->right = NULL;
return temp;
}
// function to insert elements of the
// tree to map m
void insertToHash(Node* root, unordered_set<int> &s)
{
if (!root)
return;
insertToHash(root->left, s);
s.insert(root->data);
insertToHash(root->right, s);
}
// function to check if the two BSTs contain
// same set of elements
bool checkBSTs(Node* root1, Node* root2)
{
// Base cases
if (!root1 && !root2)
return true;
if ((root1 && !root2) || (!root1 && root2))
return false;
// Create two hash sets and store
// elements both BSTs in them.
unordered_set<int> s1, s2;
insertToHash(root1, s1);
insertToHash(root2, s2);
// Return true if both hash sets
// contain same elements.
return (s1 == s2);
}
// Driver program to check above functions
int main()
{
// First BST
Node* root1 = newNode(15);
root1->left = newNode(10);
root1->right = newNode(20);
root1->left->left = newNode(5);
root1->left->right = newNode(12);
root1->right->right = newNode(25);
// Second BST
Node* root2 = newNode(15);
root2->left = newNode(12);
root2->right = newNode(20);
root2->left->left = newNode(5);
root2->left->left->right = newNode(10);
root2->right->right = newNode(25);
// check if two BSTs have same set of elements
if (checkBSTs(root1, root2))
cout << "YES";
else
cout << "NO";
return 0;
}
Java
// JAVA program to check if two BSTs contains
// same set of elements
import java.util.*;
class GFG
{
// BST Node
static class Node
{
int data;
Node left;
Node right;
};
// Utility function to create new Node
static Node newNode(int val)
{
Node temp = new Node();
temp.data = val;
temp.left = temp.right = null;
return temp;
}
// function to insert elements of the
// tree to map m
static void insertToHash(Node root, HashSet<Integer> s)
{
if (root == null)
return;
insertToHash(root.left, s);
s.add(root.data);
insertToHash(root.right, s);
}
// function to check if the two BSTs contain
// same set of elements
static boolean checkBSTs(Node root1, Node root2)
{
// Base cases
if (root1 != null && root2 != null)
return true;
if ((root1 == null && root2 != null) || (root1 != null && root2 == null))
return false;
// Create two hash sets and store
// elements both BSTs in them.
HashSet<Integer> s1 = new HashSet<Integer>();
HashSet<Integer> s2 = new HashSet<Integer>();
insertToHash(root1, s1);
insertToHash(root2, s2);
// Return true if both hash sets
// contain same elements.
return (s1.equals(s2));
}
// Driver program to check above functions
public static void main(String[] args)
{
// First BST
Node root1 = newNode(15);
root1.left = newNode(10);
root1.right = newNode(20);
root1.left.left = newNode(5);
root1.left.right = newNode(12);
root1.right.right = newNode(25);
// Second BST
Node root2 = newNode(15);
root2.left = newNode(12);
root2.right = newNode(20);
root2.left.left = newNode(5);
root2.left.left.right = newNode(10);
root2.right.right = newNode(25);
// check if two BSTs have same set of elements
if (checkBSTs(root1, root2))
System.out.print("YES");
else
System.out.print("NO");
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to check if two BSTs contains
# same set of elements
# BST Node
class Node:
def __init__(self):
self.val = 0
self.left = None
self.right = None
# Utility function to create Node
def Node_(val1):
temp = Node()
temp.val = val1
temp.left = temp.right = None
return temp
s = {}
# function to insert elements of the
# tree to map m
def insertToHash(root):
if (root == None):
return
insertToHash(root.left)
s.add(root.data)
insertToHash(root.right)
# function to check if the two BSTs contain
# same set of elements
def checkBSTs(root1, root2):
# Base cases
if (root1 != None and root2 != None) :
return True
if ((root1 == None and root2 != None) or
(root1 != None and root2 == None)):
return False
# Create two hash sets and store
# elements both BSTs in them.
s1 = {}
s2 = {}
s = s1
insertToHash(root1)
s1 = s
s = s2
insertToHash(root2)
s2 = s
# Return True if both hash sets
# contain same elements.
return (s1 == (s2))
# Driver code
# First BST
root1 = Node_(15)
root1.left = Node_(10)
root1.right = Node_(20)
root1.left.left = Node_(5)
root1.left.right = Node_(12)
root1.right.right = Node_(25)
# Second BST
root2 = Node_(15)
root2.left = Node_(12)
root2.right = Node_(20)
root2.left.left = Node_(5)
root2.left.left.right = Node_(10)
root2.right.right = Node_(25)
# check if two BSTs have same set of elements
if (checkBSTs(root1, root2)):
print("YES")
else:
print("NO")
# This code is contributed by Arnab Kundu
C#
// C# program to check if two BSTs contains
// same set of elements
using System;
using System.Collections.Generic;
class GFG
{
// BST Node
class Node
{
public int data;
public Node left;
public Node right;
};
// Utility function to create new Node
static Node newNode(int val)
{
Node temp = new Node();
temp.data = val;
temp.left = temp.right = null;
return temp;
}
// function to insert elements of the
// tree to map m
static void insertToHash(Node root,
HashSet<int> s)
{
if (root == null)
return;
insertToHash(root.left, s);
s.Add(root.data);
insertToHash(root.right, s);
}
// function to check if the two BSTs contain
// same set of elements
static bool checkBSTs(Node root1, Node root2)
{
// Base cases
if (root1 != null && root2 != null)
return true;
if ((root1 == null && root2 != null) ||
(root1 != null && root2 == null))
return false;
// Create two hash sets and store
// elements both BSTs in them.
HashSet<int> s1 = new HashSet<int>();
HashSet<int> s2 = new HashSet<int>();
insertToHash(root1, s1);
insertToHash(root2, s2);
// Return true if both hash sets
// contain same elements.
return (s1.Equals(s2));
}
// Driver Code
public static void Main(String[] args)
{
// First BST
Node root1 = newNode(15);
root1.left = newNode(10);
root1.right = newNode(20);
root1.left.left = newNode(5);
root1.left.right = newNode(12);
root1.right.right = newNode(25);
// Second BST
Node root2 = newNode(15);
root2.left = newNode(12);
root2.right = newNode(20);
root2.left.left = newNode(5);
root2.left.left.right = newNode(10);
root2.right.right = newNode(25);
// check if two BSTs have same set of elements
if (checkBSTs(root1, root2))
Console.Write("YES");
else
Console.Write("NO");
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript program to check if two BSTs contains
// same set of elements
// BST Node
class Node
{
constructor()
{
this.data = 0;
this.left = null;
this.right = null;
}
};
// Utility function to create new Node
function newNode(val)
{
var temp = new Node();
temp.data = val;
temp.left = temp.right = null;
return temp;
}
// function to insert elements of the
// tree to map m
function insertToHash(root, s)
{
if (root == null)
return;
insertToHash(root.left, s);
s.add(root.data);
insertToHash(root.right, s);
}
// function to check if the two BSTs contain
// same set of elements
function checkBSTs(root1, root2)
{
// Base cases
if (root1 != null && root2 != null)
return true;
if ((root1 == null && root2 != null) ||
(root1 != null && root2 == null))
return false;
// Create two hash sets and store
// elements both BSTs in them.
var s1 = new Set();
var s2 = new Set();
insertToHash(root1, s1);
insertToHash(root2, s2);
// Return true if both hash sets
// contain same elements.
return (s1==s2);
}
// Driver Code
// First BST
var root1 = newNode(15);
root1.left = newNode(10);
root1.right = newNode(20);
root1.left.left = newNode(5);
root1.left.right = newNode(12);
root1.right.right = newNode(25);
// Second BST
var root2 = newNode(15);
root2.left = newNode(12);
root2.right = newNode(20);
root2.left.left = newNode(5);
root2.left.left.right = newNode(10);
root2.right.right = newNode(25);
// check if two BSTs have same set of elements
if (checkBSTs(root1, root2))
document.write("YES");
else
document.write("NO");
</script>
C++
// CPP program to check if two BSTs contains
// same set of elements
#include<bits/stdc++.h>
using namespace std;
// BST Node
struct Node
{
int data;
struct Node* left;
struct Node* right;
};
// Utility function to create new Node
Node* newNode(int val)
{
Node* temp = new Node;
temp->data = val;
temp->left = temp->right = NULL;
return temp;
}
// function to insert elements of the
// tree to map m
void storeInorder(Node* root, vector<int> &v)
{
if (!root)
return;
storeInorder(root->left, v);
v.push_back(root->data);
storeInorder(root->right, v);
}
// function to check if the two BSTs contain
// same set of elements
bool checkBSTs(Node* root1, Node* root2)
{
// Base cases
if (!root1 && !root2)
return true;
if ((root1 && !root2) || (!root1 && root2))
return false;
// Create two vectors and store
// inorder traversals of both BSTs
// in them.
vector<int> v1, v2;
storeInorder(root1, v1);
storeInorder(root2, v2);
// Return true if both vectors are
// identical
return (v1 == v2);
}
// Driver program to check above functions
int main()
{
// First BST
Node* root1 = newNode(15);
root1->left = newNode(10);
root1->right = newNode(20);
root1->left->left = newNode(5);
root1->left->right = newNode(12);
root1->right->right = newNode(25);
// Second BST
Node* root2 = newNode(15);
root2->left = newNode(12);
root2->right = newNode(20);
root2->left->left = newNode(5);
root2->left->left->right = newNode(10);
root2->right->right = newNode(25);
// check if two BSTs have same set of elements
if (checkBSTs(root1, root2))
cout << "YES";
else
cout << "NO";
return 0;
}
Java
// Java program to check if two BSTs
// contain same set of elements
import java.util.*;
class GFG {
// BST Node
static class Node {
int data;
Node left;
Node right;
};
// Utility function to create new Node
static Node newNode(int val)
{
Node temp = new Node();
temp.data = val;
temp.left = temp.right = null;
return temp;
}
// function to insert elements
// of the tree to map m
static void storeInorder(Node root, Vector<Integer> v)
{
if (root == null)
return;
storeInorder(root.left, v);
v.add(root.data);
storeInorder(root.right, v);
}
// function to check if the two BSTs
// contain same set of elements
static boolean checkBSTs(Node root1, Node root2)
{
// Base cases
if (root1 == null && root2 == null)
return true;
if ((root1 == null && root2 != null)
|| (root1 != null && root2 == null))
return false;
// Create two vectors and store
// inorder traversals of both BSTs
// in them.
Vector<Integer> v1 = new Vector<Integer>();
Vector<Integer> v2 = new Vector<Integer>();
storeInorder(root1, v1);
storeInorder(root2, v2);
// Return true if both vectors are
// identical
return (v1.hashCode() == v2.hashCode());
}
// Driver Code
public static void main(String[] args)
{
// First BST
Node root1 = newNode(15);
root1.left = newNode(10);
root1.right = newNode(20);
root1.left.left = newNode(5);
root1.left.right = newNode(12);
root1.right.right = newNode(25);
// Second BST
Node root2 = newNode(15);
root2.left = newNode(12);
root2.right = newNode(20);
root2.left.left = newNode(5);
root2.left.left.right = newNode(10);
root2.right.right = newNode(25);
// check if two BSTs have same set of elements
if (checkBSTs(root1, root2))
System.out.print("YES");
else
System.out.print("NO");
}
}
// This code is contributed by Rajput-Ji
// Code corrected by Prithi_Raj
Python3
# Python3 program to check if two BSTs contains
# same set of elements
# BST Node
class Node:
def __init__(self):
self.data = 0
self.left = None
self.right = None
# Utility function to create Node
def Node_(val1):
temp = Node()
temp.data = val1
temp.left = temp.right = None
return temp
v = []
# function to insert elements of the
# tree to map m
def storeInorder(root):
if (root == None):
return
storeInorder(root.left)
v.append(root.data)
storeInorder(root.right)
# function to check if the two BSTs contain
# same set of elements
def checkBSTs(root1, root2):
# Base cases
if (root1 == None and root2 == None) :
return True
if ((root1 == None and root2 != None) or \
(root1 != None and root2 == None)):
return False
# Create two hash sets and store
# elements both BSTs in them.
v1 = []
v2 = []
v = v1
storeInorder(root1)
v1 = v
v = v2
storeInorder(root2)
v2 = v
# Return True if both hash sets
# contain same elements.
return (v1 == v2)
# Driver code
# First BST
root1 = Node_(15)
root1.left = Node_(10)
root1.right = Node_(20)
root1.left.left = Node_(5)
root1.left.right = Node_(12)
root1.right.right = Node_(25)
# Second BST
root2 = Node_(15)
root2.left = Node_(12)
root2.right = Node_(20)
root2.left.left = Node_(5)
root2.left.left.right = Node_(10)
root2.right.right = Node_(25)
# check if two BSTs have same set of elements
if (checkBSTs(root1, root2)):
print("YES")
else:
print("NO")
# This code is contributed by SHUBHAMSINGH10
C#
// C# program to check if two BSTs
// contain same set of elements
using System;
using System.Collections.Generic;
class GFG
{
// BST Node
class Node
{
public int data;
public Node left;
public Node right;
};
// Utility function to create new Node
static Node newNode(int val)
{
Node temp = new Node();
temp.data = val;
temp.left = temp.right = null;
return temp;
}
// function to insert elements
// of the tree to map m
static void storeInorder(Node root,
List<int> v)
{
if (root == null)
return;
storeInorder(root.left, v);
v.Add(root.data);
storeInorder(root.right, v);
}
// function to check if the two BSTs
// contain same set of elements
static bool checkBSTs(Node root1,
Node root2)
{
// Base cases
if (root1 == null && root2 == null)
return true;
if ((root1 == null && root2 != null) ||
(root1 != null && root2 == null))
return false;
// Create two vectors and store
// inorder traversals of both BSTs
// in them.
List<int> v1 = new List<int>();
List<int> v2 = new List<int>();
storeInorder(root1, v1);
storeInorder(root2, v2);
// Return true if both vectors are
// identical
return (v1 == v2);
}
// Driver Code
public static void Main(String[] args)
{
// First BST
Node root1 = newNode(15);
root1.left = newNode(10);
root1.right = newNode(20);
root1.left.left = newNode(5);
root1.left.right = newNode(12);
root1.right.right = newNode(25);
// Second BST
Node root2 = newNode(15);
root2.left = newNode(12);
root2.right = newNode(20);
root2.left.left = newNode(5);
root2.left.left.right = newNode(10);
root2.right.right = newNode(25);
// check if two BSTs have
// same set of elements
if (checkBSTs(root1, root2))
Console.Write("YES");
else
Console.Write("NO");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to check if two BSTs
// contain same set of elements
// BST Node
class Node {
constructor() {
this.data = 0;
this.prev = null;
this.next = null;
}
}
// Utility function to create new Node
function newNode(val)
{
var temp = new Node();
temp.data = val;
temp.left = temp.right = null;
return temp;
}
// function to insert elements
// of the tree to map m
function storeInorder(root, v) {
if (root == null)
return;
storeInorder(root.left, v);
v.push(root.data);
storeInorder(root.right, v);
}
// function to check if the two BSTs
// contain same set of elements
function checkBSTs(root1, root2)
{
// Base cases
if (root1 == null && root2 == null)
return true;
if ((root1 == null && root2 != null) ||
(root1 != null && root2 == null))
return false;
// Create two vectors and store
// inorder traversals of both BSTs
// in them.
var v1 = [];
var v2 = [];
storeInorder(root1, v1);
storeInorder(root2, v2);
// Return true if both vectors are
// identical
return (v1 == v2);
}
// Driver Code
// First BST
var root1 = newNode(15);
root1.left = newNode(10);
root1.right = newNode(20);
root1.left.left = newNode(5);
root1.left.right = newNode(12);
root1.right.right = newNode(25);
// Second BST
var root2 = newNode(15);
root2.left = newNode(12);
root2.right = newNode(20);
root2.left.left = newNode(5);
root2.left.left.right = newNode(10);
root2.right.right = newNode(25);
// check if two BSTs have same set of elements
if (checkBSTs(root1, root2))
document.write("YES");
else
document.write("NO");
// This code is contributed by Rajput-Ji
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA