Dados dos árboles de búsqueda binarios (BST), imprima los elementos de ambos BST en forma ordenada.
Nota : Ambos BST no tendrán ningún elemento común.
Ejemplos:
Input
First BST:
3
/ \
1 5
Second BST:
4
/ \
2 6
Output: 1 2 3 4 5 6
Input:
First BST:
8
/ \
2 10
/
1
Second BST:
5
/
3
/
0
Output: 0 1 2 3 5 8 10
La idea es utilizar el hecho de que el elemento más a la izquierda (primero en orden de recorrido) del árbol es el elemento mínimo en un BST. Entonces calculamos este valor para ambos árboles e imprimimos el más pequeño, ahora eliminamos este elemento impreso del árbol respectivo y lo actualizamos. Luego llamamos recursivamente a nuestra función con el árbol actualizado. Hacemos esto hasta que uno de los árboles se agota. Ahora simplemente imprimimos el recorrido en orden del otro árbol.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Structure of a BST Node
class Node {
public:
int data;
Node* left;
Node* right;
Node(int x)
{
data = x;
left = right = NULL;
}
};
// A utility function to print
// Inorder traversal of a Binary Tree
void inorder(Node* root)
{
if (root != NULL) {
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
}
// The function to print data
// of two BSTs in sorted order
void merge(Node* root1, Node* root2)
{
// Base cases
if (!root1 && !root2)
return;
// If the first tree is exhausted
// simply print the inorder
// traversal of the second tree
if (!root1) {
inorder(root2);
return;
}
// If second tree is exhausted
// simply print the inoreder
// traversal of the first tree
if (!root2) {
inorder(root1);
return;
}
// A temporary pointer currently
// pointing to root of first tree
Node* temp1 = root1;
// previous pointer to store the
// parent of temporary pointer
Node* prev1 = NULL;
// Traverse through the first tree until you reach
// the leftmost element, which is the first element
// of the tree in the inorder traversal.
// This is the least element of the tree
while (temp1->left) {
prev1 = temp1;
temp1 = temp1->left;
}
// Another temporary pointer currently
// pointing to root of second tree
Node* temp2 = root2;
// Previous pointer to store the
// parent of second temporary pointer
Node* prev2 = NULL;
// Traverse through the second tree until you reach
// the leftmost element, which is the first element of
// the tree in inorder traversal.
// This is the least element of the tree.
while (temp2->left) {
prev2 = temp2;
temp2 = temp2->left;
}
// Compare the least current least
// elements of both the tree
if (temp1->data <= temp2->data) {
// If first tree's element is smaller print it
cout << temp1->data << " ";
// If the node has no parent, that
// means this node is the root
if (prev1 == NULL) {
// Simply make the right
// child of the root as new root
merge(root1->right, root2);
}
// If node has a parent
else {
// As this node is the leftmost node,
// it is certain that it will not have
// a let child so we simply assign this
// node's right pointer, which can be
// either null or not, to its parent's left
// pointer. This statement is
// just doing the task of deleting the node
prev1->left = temp1->right;
// recursively call the merge
// function with updated tree
merge(root1, root2);
}
}
else {
cout << temp2->data << " ";
// If the node has no parent, that
// means this node is the root
if (prev2 == NULL) {
// Simply make the right child
// of root as new root
merge(root1, root2->right);
}
// If node has a parent
else {
prev2->left = temp2->right;
// Recursively call the merge
// function with updated tree
merge(root1, root2);
}
}
}
// Driver Code
int main()
{
Node *root1 = NULL, *root2 = NULL;
root1 = new Node(3);
root1->left = new Node(1);
root1->right = new Node(5);
root2 = new Node(4);
root2->left = new Node(2);
root2->right = new Node(6);
// Print sorted nodes of both trees
merge(root1, root2);
return 0;
}
Java
// Java implementation of above approach
import java.util.*;
class GFG{
// Structure of a BST Node
static class Node
{
int data;
Node left;
Node right;
};
static Node newNode(int num)
{
Node temp = new Node();
temp.data = num;
temp.left = temp.right = null;
return temp;
}
// A utility function to print
// Inorder traversal of a Binary Tree
static void inorder(Node root)
{
if (root != null)
{
inorder(root.left);
System.out.print(root.data + " ");
inorder(root.right);
}
}
// The function to print data
// of two BSTs in sorted order
static void merge(Node root1, Node root2)
{
// Base cases
if (root1 == null && root2 == null)
return;
// If the first tree is exhausted
// simply print the inorder
// traversal of the second tree
if (root1 == null)
{
inorder(root2);
return;
}
// If second tree is exhausted
// simply print the inoreder
// traversal of the first tree
if (root2 == null)
{
inorder(root1);
return;
}
// A temporary pointer currently
// pointing to root of first tree
Node temp1 = root1;
// previous pointer to store the
// parent of temporary pointer
Node prev1 = null;
// Traverse through the first tree
// until you reach the leftmost element,
// which is the first element of the tree
// in the inorder traversal.
// This is the least element of the tree
while (temp1.left != null)
{
prev1 = temp1;
temp1 = temp1.left;
}
// Another temporary pointer currently
// pointing to root of second tree
Node temp2 = root2;
// Previous pointer to store the
// parent of second temporary pointer
Node prev2 = null;
// Traverse through the second tree
// until you reach the leftmost element,
// which is the first element of
// the tree in inorder traversal.
// This is the least element of the tree.
while (temp2.left != null)
{
prev2 = temp2;
temp2 = temp2.left;
}
// Compare the least current least
// elements of both the tree
if (temp1.data <= temp2.data)
{
// If first tree's element is
// smaller print it
System.out.print(temp1.data + " ");
// If the node has no parent, that
// means this node is the root
if (prev1 == null)
{
// Simply make the right
// child of the root as new root
merge(root1.right, root2);
}
// If node has a parent
else
{
// As this node is the leftmost node,
// it is certain that it will not have
// a let child so we simply assign this
// node's right pointer, which can be
// either null or not, to its parent's left
// pointer. This statement is
// just doing the task of deleting the node
prev1.left = temp1.right;
// recursively call the merge
// function with updated tree
merge(root1, root2);
}
}
else
{
System.out.print(temp2.data + " ");
// If the node has no parent, that
// means this node is the root
if (prev2 == null)
{
// Simply make the right child
// of root as new root
merge(root1, root2.right);
}
// If node has a parent
else
{
prev2.left = temp2.right;
// Recursively call the merge
// function with updated tree
merge(root1, root2);
}
}
}
// Driver Code
public static void main(String args[])
{
Node root1 = null, root2 = null;
root1 = newNode(3);
root1.left = newNode(1);
root1.right = newNode(5);
root2 = newNode(4);
root2.left = newNode(2);
root2.right = newNode(6);
// Print sorted nodes of both trees
merge(root1, root2);
}
}
// This code is contributed by ipg2016107
Python3
# Python3 implementation of above approach # Node of the binary tree class node: def __init__ (self, key): self.data = key self.left = None self.right = None # A utility function to print # Inorder traversal of a Binary Tree def inorder(root): if (root != None): inorder(root.left) print(root.data, end = " ") inorder(root.right) # The function to print data # of two BSTs in sorted order def merge(root1, root2): # Base cases if (not root1 and not root2): return # If the first tree is exhausted # simply print the inorder # traversal of the second tree if (not root1): inorder(root2) return # If second tree is exhausted # simply print the inoreder # traversal of the first tree if (not root2): inorder(root1) return # A temporary pointer currently # pointing to root of first tree temp1 = root1 # previous pointer to store the # parent of temporary pointer prev1 = None # Traverse through the first tree # until you reach the leftmost # element, which is the first element # of the tree in the inorder traversal. # This is the least element of the tree while (temp1.left): prev1 = temp1 temp1 = temp1.left # Another temporary pointer currently # pointing to root of second tree temp2 = root2 # Previous pointer to store the # parent of second temporary pointer prev2 = None # Traverse through the second tree # until you reach the leftmost element, # which is the first element of the # tree in inorder traversal. This is # the least element of the tree. while (temp2.left): prev2 = temp2 temp2 = temp2.left # Compare the least current least # elements of both the tree if (temp1.data <= temp2.data): # If first tree's element is # smaller print it print(temp1.data, end = " ") # If the node has no parent, that # means this node is the root if (prev1 == None): # Simply make the right # child of the root as new root merge(root1.right, root2) # If node has a parent else: # As this node is the leftmost node, # it is certain that it will not have # a let child so we simply assign this # node's right pointer, which can be # either null or not, to its parent's left # pointer. This statement is # just doing the task of deleting the node prev1.left = temp1.right # recursively call the merge # function with updated tree merge(root1, root2) else: print(temp2.data, end = " ") # If the node has no parent, that # means this node is the root if (prev2 == None): # Simply make the right child # of root as new root merge(root1, root2.right) # If node has a parent else: prev2.left = temp2.right # Recursively call the merge # function with updated tree merge(root1, root2) # Driver Code if __name__ == '__main__': root1 = None root2 = None root1 = node(3) root1.left = node(1) root1.right = node(5) root2 = node(4) root2.left = node(2) root2.right = node(6) # Print sorted nodes of both trees merge(root1, root2) # This code is contributed by mohit kumar 29
C#
// C# implementation of above approach
using System;
// Structure of a BST Node
public class Node
{
public int data;
public Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
class GFG{
static Node root1;
static Node root2;
// A utility function to print
// Inorder traversal of a Binary Tree
static void inorder(Node root)
{
if (root != null)
{
inorder(root.left);
Console.WriteLine(root.data + " ");
inorder(root.right);
}
}
// The function to print data
// of two BSTs in sorted order
static void merge(Node root1, Node root2)
{
// Base cases
if (root1 == null && root2 == null)
{
return;
}
// If the first tree is exhausted
// simply print the inorder traversal
// of the second tree
if (root1 == null)
{
inorder(root2);
return;
}
// If second tree is exhausted
// simply print the inoreder
// traversal of the first tree
if (root2 == null)
{
inorder(root1);
return;
}
// A temporary pointer currently
// pointing to root of first tree
Node temp1 = root1;
// previous pointer to store the
// parent of temporary pointer
Node prev1 = null;
// Traverse through the first tree
// until you reach the leftmost element,
// which is the first element of the tree
// in the inorder traversal.
// This is the least element of the tree
while (temp1.left != null)
{
prev1 = temp1;
temp1 = temp1.left;
}
// Another temporary pointer currently
// pointing to root of second tree
Node temp2 = root2;
// Previous pointer to store the
// parent of second temporary pointer
Node prev2 = null;
// Traverse through the second tree until
// you reach the leftmost element, which
// is the first element of the tree in
// inorder traversal. This is the least
// element of the tree.
while (temp2.left != null)
{
prev2 = temp2;
temp2 = temp2.left;
}
// Compare the least current least
// elements of both the tree
if (temp1.data <= temp2.data)
{
// If first tree's element is
// smaller print it
Console.Write(temp1.data + " ");
// If the node has no parent, that
// means this node is the root
if (prev1 == null)
{
// Simply make the right
// child of the root as new root
merge(root1.right, root2);
}
// If node has a parent
else
{
// As this node is the leftmost node,
// it is certain that it will not have
// a let child so we simply assign this
// node's right pointer, which can be
// either null or not, to its parent's
// left pointer. This statement is just
// doing the task of deleting the node
prev1.left = temp1.right;
// Recursively call the merge
// function with updated tree
merge(root1, root2);
}
}
else
{
Console.Write(temp2.data + " ");
// If the node has no parent, that
// means this node is the root
if (prev2 == null)
{
// Simply make the right child
// of root as new root
merge(root1, root2.right);
}
// If node has a parent
else
{
prev2.left = temp2.right;
// Recursively call the merge
// function with updated tree
merge(root1, root2);
}
}
}
// Driver Code
static public void Main()
{
GFG.root1 = new Node(3);
GFG.root1.left = new Node(1);
GFG.root1.right = new Node(5);
GFG.root2 = new Node(4);
GFG.root2.left = new Node(2);
GFG.root2.right = new Node(6);
// Print sorted nodes of both trees
merge(root1, root2);
}
}
// This code is contributed by avanitrachhadiya2155
Javascript
<script>
// Javascript implementation of above approach
// Structure of a BST Node
class Node
{
constructor(num)
{
this.data=num;
this.left=this.right=null;
}
}
// A utility function to print
// Inorder traversal of a Binary Tree
function inorder(root)
{
if (root != null)
{
inorder(root.left);
document.write(root.data + " ");
inorder(root.right);
}
}
// The function to print data
// of two BSTs in sorted order
function merge(root1,root2)
{
// Base cases
if (root1 == null && root2 == null)
return;
// If the first tree is exhausted
// simply print the inorder
// traversal of the second tree
if (root1 == null)
{
inorder(root2);
return;
}
// If second tree is exhausted
// simply print the inoreder
// traversal of the first tree
if (root2 == null)
{
inorder(root1);
return;
}
// A temporary pointer currently
// pointing to root of first tree
let temp1 = root1;
// previous pointer to store the
// parent of temporary pointer
let prev1 = null;
// Traverse through the first tree
// until you reach the leftmost element,
// which is the first element of the tree
// in the inorder traversal.
// This is the least element of the tree
while (temp1.left != null)
{
prev1 = temp1;
temp1 = temp1.left;
}
// Another temporary pointer currently
// pointing to root of second tree
let temp2 = root2;
// Previous pointer to store the
// parent of second temporary pointer
let prev2 = null;
// Traverse through the second tree
// until you reach the leftmost element,
// which is the first element of
// the tree in inorder traversal.
// This is the least element of the tree.
while (temp2.left != null)
{
prev2 = temp2;
temp2 = temp2.left;
}
// Compare the least current least
// elements of both the tree
if (temp1.data <= temp2.data)
{
// If first tree's element is
// smaller print it
document.write(temp1.data + " ");
// If the node has no parent, that
// means this node is the root
if (prev1 == null)
{
// Simply make the right
// child of the root as new root
merge(root1.right, root2);
}
// If node has a parent
else
{
// As this node is the leftmost node,
// it is certain that it will not have
// a let child so we simply assign this
// node's right pointer, which can be
// either null or not, to its parent's left
// pointer. This statement is
// just doing the task of deleting the node
prev1.left = temp1.right;
// recursively call the merge
// function with updated tree
merge(root1, root2);
}
}
else
{
document.write(temp2.data + " ");
// If the node has no parent, that
// means this node is the root
if (prev2 == null)
{
// Simply make the right child
// of root as new root
merge(root1, root2.right);
}
// If node has a parent
else
{
prev2.left = temp2.right;
// Recursively call the merge
// function with updated tree
merge(root1, root2);
}
}
}
// Driver Code
let root1 = null, root2 = null;
root1 = new Node(3);
root1.left = new Node(1);
root1.right = new Node(5);
root2 = new Node(4);
root2.left = new Node(2);
root2.right = new Node(6);
// Print sorted nodes of both trees
merge(root1, root2);
// This code is contributed by unknown2108
</script>
Producción
1 2 3 4 5 6
Complejidad temporal: O((M+N)(h1+h2)), donde M y N son el número de Nodes de los dos árboles y, h1 y h2 son las alturas del árbol respectivamente.
Espacio Auxiliar: O(N)
Método 2: Usando Morris Traversal de los árboles
La solución anterior usa recursividad y por lo tanto requiere espacio auxiliar O(N). Podemos usar el concepto de Morris Traversal para mejorar la complejidad espacial del algoritmo eliminando el uso de pilas. El recorrido de Morris es un método para recorrer un árbol binario sin utilizar la recursividad y con un espacio extra constante (O(1)).
La idea es atravesar hasta el Node de datos más pequeño de ambos árboles utilizando el recorrido de Morris y comparar los Nodes en ambos árboles. Usamos el más pequeño para agregar a la array de respuesta y moverlo al siguiente Node en orden. Sabemos que el recorrido en orden de los árboles binarios de búsqueda está ordenado. Por lo tanto, podemos movernos al Node más pequeño y continuar moviéndonos en orden para llegar al siguiente Node más alto.
Algoritmo:
- Aplique el recorrido de Morris en root1:
- Compruebe si la raíz tiene un Node izquierdo y si tiene un Node izquierdo.
- Vaya al Node más a la derecha del Node izquierdo.
- En el Node más a la derecha de la izquierda, asigne su puntero derecho a la raíz.
- Hacer izquierda = raíz->izquierda y hacer raíz->izquierda = NULL
- Mover raíz a la izquierda.
- Repita hasta que la raíz tenga un Node izquierdo
- Si no tiene un Node izquierdo, eso significa que root es el Node más pequeño, por lo que rompe el recorrido de Morris de root1.
- Compruebe si la raíz tiene un Node izquierdo y si tiene un Node izquierdo.
- Aplique el mismo recorrido de Morris para root2.
- Ahora root1 y root2 están en los Nodes más pequeños de sus respectivos árboles. Compare los datos de root1 con los datos de root2:
- Si los datos de root1 son menores o iguales que los datos de root2: agregue los datos de root1 a nuestra array de respuestas y mueva root1 a su derecha.
- De lo contrario, agregue datos de root2 a nuestra array de respuestas y mueva root2 a su derecha.
- Si en el paso 3, root1 o root2 es NULL, eso significa que el árbol está agotado y hemos agregado todos los Nodes para responder a la array, por lo que solo agregamos los datos restantes del árbol para responder a la array sin comparación y los movemos a su derecha.
- Repita los pasos 1 a 4 hasta que ambos árboles estén agotados.
C++
#include <bits/stdc++.h>
using namespace std;
// Structure of a BST Node
class Node {
public:
int data;
Node *left, *right;
// Constructor
Node(int data){
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
void mergeBSTs(Node*, Node*);
int main(){
/* Let us create the following tree as first tree
3
/ \
1 5
*/
Node* root1 = new Node(3);
root1->left = new Node(1);
root1->right = new Node(5);
/* Let us create the following tree as second tree
4
/ \
2 6
*/
Node* root2 = new Node(4);
root2->left = new Node(2);
root2->right = new Node(6);
// Merging the BSTs
mergeBSTs(root1, root2);
}
void mergeBSTs(Node* root1, Node* root2){
// We run this loop until both trees are completely
// exhausted Even if one of the trees is still left, we
// run this loop
while (root1 || root2) {
// Morris traversal of the first tree
while (root1) { // This check is to ensure that if
// root1 is already exhausted we skip root1
// If root has a left node, we go to the
// rightmost child of the left node and assign
// root to the right of the rightmost node
if (root1->left) {
Node* left = root1->left;
// Moving to the rightmost node of left
while (left->right)
left = left->right;
// Assign root to right of rightmost node
left->right = root1;
// Make root's left to NULL and move root to left
left = root1->left;
root1->left = NULL;
root1 = left;
}
else break; // If root doesn't have a left node, that means
// we're already on the left most (smallest) node
}
// Morris traversal of the second tree
while (root2) { // This check is to ensure that if
// root2 is already exhausted we skip root2
// If root has a left node, we go to the
// rightmost child of the left node and assign
// root to the right of the rightmost node
if (root2->left) {
Node* left = root2->left;
// Moving to the rightmost node of left
while (left->right)
left = left->right;
// Assign root to right of rightmost node
left->right = root2;
// Make root's left to NULL and move root to left
left = root2->left;
root2->left = NULL;
root2 = left;
}
else break; // If root doesn't have a left node, that means
// we're already on the left most (smallest) node
}
// Here root1 and root2 are smallest nodes in both trees
if (root1 && root2) {
// Compare both nodes' data
if (root1->data <= root2->data) {
cout << root1->data << " "; // Add smaller one to ans array
root1 = root1->right; // Move smaller one to right
}
else {
cout << root2->data << " "; // Add smaller one to ans array
root2 = root2->right; // Move smaller one to right
}
}
else if (root1) { // If root2 has exhausted and only root1 remains
cout << root1->data << " "; // Add it to ans array
root1 = root1->right; // Move it to right
}
else if (root2) { // If root2 has exhausted and only root2 remains
cout << root2->data << " "; // Add it to ans array
root2 = root2->right; // Move it to right
}
}
}
Java
import java.util.*;
class GFG{
// Structure of a BST Node
static class Node {
int data;
Node left, right;
// Constructor
Node(int data){
this.data = data;
this.left = null;
this.right = null;
}
};
public static void main(String[] args){
/* Let us create the following tree as first tree
3
/ \
1 5
*/
Node root1 = new Node(3);
root1.left = new Node(1);
root1.right = new Node(5);
/* Let us create the following tree as second tree
4
/ \
2 6
*/
Node root2 = new Node(4);
root2.left = new Node(2);
root2.right = new Node(6);
// Merging the BSTs
mergeBSTs(root1, root2);
}
static void mergeBSTs(Node root1, Node root2)
{
// We run this loop until both trees are completely
// exhausted Even if one of the trees is still left, we
// run this loop
while (root1 != null || root2 != null)
{
// Morris traversal of the first tree
while (root1 != null)
{
// This check is to ensure that if
// root1 is already exhausted we skip root1
// If root has a left node, we go to the
// rightmost child of the left node and assign
// root to the right of the rightmost node
if (root1.left != null)
{
Node left = root1.left;
// Moving to the rightmost node of left
while (left.right != null)
left = left.right;
// Assign root to right of rightmost node
left.right = root1;
// Make root's left to null and move root to left
left = root1.left;
root1.left = null;
root1 = left;
}
else break; // If root doesn't have a left node, that means
// we're already on the left most (smallest) node
}
// Morris traversal of the second tree
while (root2!=null) { // This check is to ensure that if
// root2 is already exhausted we skip root2
// If root has a left node, we go to the
// rightmost child of the left node and assign
// root to the right of the rightmost node
if (root2.left!=null) {
Node left = root2.left;
// Moving to the rightmost node of left
while (left.right!=null)
left = left.right;
// Assign root to right of rightmost node
left.right = root2;
// Make root's left to null and move root to left
left = root2.left;
root2.left = null;
root2 = left;
}
else break; // If root doesn't have a left node, that means
// we're already on the left most (smallest) node
}
// Here root1 and root2 are smallest nodes in both trees
if (root1!=null && root2!=null) {
// Compare both nodes' data
if (root1.data <= root2.data) {
System.out.print(root1.data+ " "); // Add smaller one to ans array
root1 = root1.right; // Move smaller one to right
}
else {
System.out.print(root2.data+ " "); // Add smaller one to ans array
root2 = root2.right; // Move smaller one to right
}
}
else if (root1 != null) { // If root2 has exhausted and only root1 remains
System.out.print(root1.data+ " "); // Add it to ans array
root1 = root1.right; // Move it to right
}
else if (root2 != null) { // If root2 has exhausted and only root2 remains
System.out.print(root2.data+ " "); // Add it to ans array
root2 = root2.right; // Move it to right
}
}
}
}
// This code is contributed by Rajput-Ji
Python3
# Python code for the above approach class node: def __init__(self, key): self.data = key self.left = None self.right = None def mergeBSTs(root1, root2): # We run this loop until both trees are completely # exhausted Even if one of the trees is still left, we # run this loop while (root1 or root2): # Morris traversal of the first tree while(root1): # This check is to ensure that if # root1 is already exhausted we skip root1 # If root has a left node, we go to the # rightmost child of the left node and assign # root to the right of the rightmost node if(root1.left): left = root1.left # Moving to the rightmost node of left while (left.right): left = left.right # Assign root to right of rightmost node left.right = root1 # Make root's left to null and move root to left left = root1.left root1.left = None root1 = left else: # If root doesn't have a left node, that means # we're already on the left most (smallest) node break # Morris traversal of the second tree while(root2): # This check is to ensure that if # root2 is already exhausted we skip root2 # If root has a left node, we go to the # rightmost child of the left node and assign # root to the right of the rightmost node if (root2.left): left = root2.left # Moving to the rightmost node of left while(left.right): left = left.right # Assign root to right of rightmost node left.right = root2 # Make root's left to null and move root to left left = root2.left root2.left = None root2 = left else: break # Here root1 and root2 are smallest nodes in both trees if(root1 and root2): # Compare both nodes' data if(root1.data <= root2.data): print(root1.data, end=" ") # Add smaller one to ans array root1 = root1.right # Move smaller one to right else: print(root2.data, end=" ") # Add smaller one to ans array root2 = root2.right # Move smaller one to right elif(root1): # If root2 has exhausted and only root1 remains print(root1.data, end=" ") # Add it to ans array root1 = root1.right # Move it to right elif(root2): # If root2 has exhausted and only root2 remains print(root2.data, end=" ") # Add it to ans array root2 = root2.right # Move it to right if __name__ == '__main__': root1 = None root2 = None # Let us create the following tree as first tree # 3 # / \ # 1 5 root1 = node(3) root1.left = node(1) root1.right = node(5) # Let us create the following tree as first tree # 4 # / \ # 2 6 root2 = node(4) root2.left = node(2) root2.right = node(6) # Merging the BSTs mergeBSTs(root1, root2) # This code is contributed by lokesh (lokeshmvs21).
C#
using System;
public class GFG {
// Structure of a BST Node
public class Node {
public int data;
public Node left, right;
// Constructor
public Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
};
public static void Main(String[] args) {
/*
* Let us create the following tree as first tree 3 / \ 1 5
*/
Node root1 = new Node(3);
root1.left = new Node(1);
root1.right = new Node(5);
/*
* Let us create the following tree as second tree 4 / \ 2 6
*/
Node root2 = new Node(4);
root2.left = new Node(2);
root2.right = new Node(6);
// Merging the BSTs
mergeBSTs(root1, root2);
}
static void mergeBSTs(Node root1, Node root2) {
// We run this loop until both trees are completely
// exhausted Even if one of the trees is still left, we
// run this loop
while (root1 != null || root2 != null) {
// Morris traversal of the first tree
while (root1 != null) {
// This check is to ensure that if
// root1 is already exhausted we skip root1
// If root has a left node, we go to the
// rightmost child of the left node and assign
// root to the right of the rightmost node
if (root1.left != null) {
Node left = root1.left;
// Moving to the rightmost node of left
while (left.right != null)
left = left.right;
// Assign root to right of rightmost node
left.right = root1;
// Make root's left to null and move root to left
left = root1.left;
root1.left = null;
root1 = left;
} else
break; // If root doesn't have a left node, that means
// we're already on the left most (smallest) node
}
// Morris traversal of the second tree
while (root2 != null)
{
// This check is to ensure that if
// root2 is already exhausted we skip root2
// If root has a left node, we go to the
// rightmost child of the left node and assign
// root to the right of the rightmost node
if (root2.left != null) {
Node left = root2.left;
// Moving to the rightmost node of left
while (left.right != null)
left = left.right;
// Assign root to right of rightmost node
left.right = root2;
// Make root's left to null and move root to left
left = root2.left;
root2.left = null;
root2 = left;
} else
break; // If root doesn't have a left node, that means
// we're already on the left most (smallest) node
}
// Here root1 and root2 are smallest nodes in both trees
if (root1 != null && root2 != null)
{
// Compare both nodes' data
if (root1.data <= root2.data) {
Console.Write(root1.data + " "); // Add smaller one to ans array
root1 = root1.right; // Move smaller one to right
} else {
Console.Write(root2.data + " "); // Add smaller one to ans array
root2 = root2.right; // Move smaller one to right
}
} else if (root1 != null)
{
// If root2 has exhausted and only root1 remains
Console.Write(root1.data + " "); // Add it to ans array
root1 = root1.right; // Move it to right
} else if (root2 != null)
{
// If root2 has exhausted and only root2 remains
Console.Write(root2.data + " "); // Add it to ans array
root2 = root2.right; // Move it to right
}
}
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Structure of a BST Node
class Node
{
// Constructor
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}
function mergeBSTs(root1, root2)
{
// We run this loop until both trees are completely
// exhausted Even if one of the trees is still left, we
// run this loop
while (root1 != null || root2 != null) {
// Morris traversal of the first tree
while (root1 != null) {
// This check is to ensure that if
// root1 is already exhausted we skip root1
// If root has a left node, we go to the
// rightmost child of the left node and assign
// root to the right of the rightmost node
if (root1.left != null) {
var left = root1.left;
// Moving to the rightmost node of left
while (left.right != null)
left = left.right;
// Assign root to right of rightmost node
left.right = root1;
// Make root's left to null and move root to left
left = root1.left;
root1.left = null;
root1 = left;
} else
break; // If root doesn't have a left node, that means
// we're already on the left most (smallest) node
}
// Morris traversal of the second tree
while (root2 != null) { // This check is to ensure that if
// root2 is already exhausted we skip root2
// If root has a left node, we go to the
// rightmost child of the left node and assign
// root to the right of the rightmost node
if (root2.left != null) {
var left = root2.left;
// Moving to the rightmost node of left
while (left.right != null)
left = left.right;
// Assign root to right of rightmost node
left.right = root2;
// Make root's left to null and move root to left
left = root2.left;
root2.left = null;
root2 = left;
} else
break; // If root doesn't have a left node, that means
// we're already on the left most (smallest) node
}
// Here root1 and root2 are smallest nodes in both trees
if (root1 != null && root2 != null) {
// Compare both nodes' data
if (root1.data <= root2.data) {
document.write(root1.data + " "); // Add smaller one to ans array
root1 = root1.right; // Move smaller one to right
} else {
document.write(root2.data + " "); // Add smaller one to ans array
root2 = root2.right; // Move smaller one to right
}
} else if (root1 != null) { // If root2 has exhausted and only root1 remains
document.write(root1.data + " "); // Add it to ans array
root1 = root1.right; // Move it to right
} else if (root2 != null) { // If root2 has exhausted and only root2 remains
document.write(root2.data + " "); // Add it to ans array
root2 = root2.right; // Move it to right
}
}
}
/*
* Let us create the following tree as first tree
3
/ \
1 5
*/
var root1 = new Node(3);
root1.left = new Node(1);
root1.right = new Node(5);
/*
* Let us create the following tree as second tree
4
/ \
2 6
*/
var root2 = new Node(4);
root2.left = new Node(2);
root2.right = new Node(6);
// Merging the BSTs
mergeBSTs(root1, root2);
// This code is contributed by Rajput-Ji
</script>
Producción
1 2 3 4 5 6
Complejidad temporal: O(m + n)
Complejidad del Espacio Auxiliar: O(1).
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por Abhishek_Vashisht y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA