Imprimir Nodes comunes en dos árboles de búsqueda binarios

Dados dos árboles de búsqueda binarios, encuentre Nodes comunes en ellos. En otras palabras, encuentre la intersección de dos BST.

Ejemplo:

Método 1 (Solución simple) Una forma simple es buscar uno por uno todos los Nodes del primer árbol en el segundo árbol. La complejidad temporal de esta solución es O(m * h) donde m es el número de Nodes en el primer árbol yh es la altura del segundo árbol.

Método 2 :

• Enfoque: si pensamos en otro problema en el que se nos dan dos arrays ordenadas y tenemos que encontrar la intersección entre ellas, podemos hacerlo fácilmente usando la técnica de dos punteros. Ahora podemos convertir fácilmente este problema en el anterior. Sabemos que si almacenamos el recorrido en orden de un BST en una array, esa array se ordenará en orden ascendente. Entonces, lo que podemos hacer es simplemente tomar el recorrido en orden de ambos árboles y almacenarlos en dos arrays separadas y luego encontrar la intersección entre dos arrays.
• Algoritmo:
  1) Realice un recorrido en orden del primer árbol y almacene el recorrido en una array auxiliar ar1 []. Ver sortedInorder() aquí .
  2) Haga un recorrido en orden del segundo árbol y almacene el recorrido en una array auxiliar ar2[]
  3) Encuentre la intersección de ar1[] y ar2[]. Vea esto para más detalles.
• Análisis de Complejidad:
  • Complejidad Temporal: O(m+n).
    Aquí ‘m’ y ‘n’ son el número de Nodes en el primer y segundo árbol respectivamente, ya que necesitamos atravesar ambos árboles.
  • Espacio auxiliar: no se usa ninguna estructura de datos para almacenar valores: O (m + n)
    La razón es que necesitamos dos arrays separadas para almacenar recorridos en orden de ambos árboles.

Método 3 (Tiempo lineal y espacio adicional limitado)
La idea es utilizar un recorrido en orden iterativo

• Enfoque:
  La idea aquí es optimizar el espacio. En el enfoque anterior, almacenamos todos los elementos del árbol y luego los comparamos, pero la pregunta es si es realmente necesario almacenar todos los elementos. Lo que uno puede hacer es almacenar una rama particular del árbol (en el peor de los casos, ‘Altura del árbol’) y luego comenzar a comparar. Podemos tomar dos pilas y almacenar en orden el recorrido de los árboles en las respectivas pilas, pero el número máximo de elementos debe ser igual a esa rama particular del árbol. Tan pronto como termina esa rama, comenzamos a hacer estallar y comparar los elementos de la pila. Ahora si arriba (pila-1) <arriba (pila-2)puede haber más elementos en la rama derecha de top(stack-1) que son mayores que él y pueden ser iguales a top(stack-2). Así que insertamos la rama derecha de la parte superior (pila-1) hasta que sea igual a NULL. Al final de cada una de estas inserciones, tenemos tres condiciones para verificar y luego hacemos las inserciones en la pila en consecuencia.

  if top(stack-1)<top(stack-2)
  root1=root1->right (then do insertions)
  
  if top(stack-1)>top(stack-2)
  root2=root2->right (then do insertions)
  
  else
  It's a match
  

C++

// C++ program of iterative traversal based method to // find common elements in two BSTs. #include<iostream> #include<stack> using namespace std;    // A BST node struct Node {     int key;     struct Node *left, *right; };    // A utility function to create a new node Node *newNode(int ele) {     Node *temp = new Node;     temp->key = ele;     temp->left = temp->right = NULL;     return temp; }    // Function two print common elements in given two trees void printCommon(Node *root1, Node *root2) {     // Create two stacks for two inorder traversals     stack<Node *> stack1, s1, s2;        while (1)     {         // push the Nodes of first tree in stack s1         if (root1)         {             s1.push(root1);             root1 = root1->left;         }            // push the Nodes of second tree in stack s2         else if (root2)         {             s2.push(root2);             root2 = root2->left;         }            // Both root1 and root2 are NULL here         else if (!s1.empty() && !s2.empty())         {             root1 = s1.top();             root2 = s2.top();                // If current keys in two trees are same             if (root1->key == root2->key)             {                 cout << root1->key << " ";                 s1.pop();                 s2.pop();                    // move to the inorder successor                 root1 = root1->right;                 root2 = root2->right;             }                else if (root1->key < root2->key)             {                 // If Node of first tree is smaller, than that of                 // second tree, then its obvious that the inorder                 // successors of current Node can have same value                 // as that of the second tree Node. Thus, we pop                 // from s2                 s1.pop();                 root1 = root1->right;                    // root2 is set to NULL, because we need                 // new Nodes of tree 1                 root2 = NULL;             }             else if (root1->key > root2->key)             {                 s2.pop();                 root2 = root2->right;                 root1 = NULL;             }         }            // Both roots and both stacks are empty         else  break;     } }    // A utility function to do inorder traversal void inorder(struct Node *root) {     if (root)     {         inorder(root->left);         cout<<root->key<<" ";         inorder(root->right);     } }    /* 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; }    // Driver program int main() {     // Create first tree as shown in example     Node *root1 = NULL;     root1 = insert(root1, 5);     root1 = insert(root1, 1);     root1 = insert(root1, 10);     root1 = insert(root1,  0);     root1 = insert(root1,  4);     root1 = insert(root1,  7);     root1 = insert(root1,  9);        // Create second tree as shown in example     Node *root2 = NULL;     root2 = insert(root2, 10);     root2 = insert(root2, 7);     root2 = insert(root2, 20);     root2 = insert(root2, 4);     root2 = insert(root2, 9);        cout << "Tree 1 : ";     inorder(root1);     cout << endl;        cout << "Tree 2 : ";     inorder(root2);        cout << "\nCommon Nodes: ";     printCommon(root1, root2);        return 0; }

Java

// Java program of iterative traversal based method to  // find common elements in two BSTs. import java.util.*; class GfG {     // A BST node  static class Node  {      int key;      Node left, right;  }    // A utility function to create a new node  static Node newNode(int ele)  {      Node temp = new Node();      temp.key = ele;      temp.left = null;     temp.right = null;      return temp;  }     // Function two print common elements in given two trees  static void printCommon(Node root1, Node root2)  {             Stack<Node> s1 = new Stack<Node>();      Stack<Node> s2 = new Stack<Node>();        while (true)      {          // push the Nodes of first tree in stack s1          if (root1 != null)          {              s1.push(root1);              root1 = root1.left;          }             // push the Nodes of second tree in stack s2          else if (root2 != null)          {              s2.push(root2);              root2 = root2.left;          }             // Both root1 and root2 are NULL here          else if (!s1.isEmpty() && !s2.isEmpty())          {              root1 = s1.peek();              root2 = s2.peek();                 // If current keys in two trees are same              if (root1.key == root2.key)              {                  System.out.print(root1.key + " ");                  s1.pop();                  s2.pop();                     // move to the inorder successor                  root1 = root1.right;                  root2 = root2.right;              }                 else if (root1.key < root2.key)              {                  // If Node of first tree is smaller, than that of                  // second tree, then its obvious that the inorder                  // successors of current Node can have same value                  // as that of the second tree Node. Thus, we pop                  // from s2                  s1.pop();                  root1 = root1.right;                     // root2 is set to NULL, because we need                  // new Nodes of tree 1                  root2 = null;              }              else if (root1.key > root2.key)              {                  s2.pop();                  root2 = root2.right;                  root1 = null;              }          }             // Both roots and both stacks are empty          else break;      }  }     // A utility function to do inorder traversal  static void inorder(Node root)  {      if (root != null)      {          inorder(root.left);          System.out.print(root.key + " ");          inorder(root.right);      }  }     /* 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;  }     // Driver program  public static void main(String[] args)  {      // Create first tree as shown in example      Node root1 = null;      root1 = insert(root1, 5);      root1 = insert(root1, 1);      root1 = insert(root1, 10);      root1 = insert(root1, 0);      root1 = insert(root1, 4);      root1 = insert(root1, 7);      root1 = insert(root1, 9);         // Create second tree as shown in example      Node root2 = null;      root2 = insert(root2, 10);      root2 = insert(root2, 7);      root2 = insert(root2, 20);      root2 = insert(root2, 4);      root2 = insert(root2, 9);         System.out.print("Tree 1 : " + "\n");      inorder(root1);      System.out.println();     System.out.print("Tree 2 : " + "\n");      inorder(root2);      System.out.println();     System.out.println("Common Nodes: ");        printCommon(root1, root2);     } }

Python3

# Python3 program of iterative traversal based  # method to find common elements in two BSTs.     # A utility function to create a new node  class newNode:     def __init__(self, key):         self.key = key         self.left = self.right = None    # Function two print common elements  # in given two trees  def printCommon(root1, root2):            # Create two stacks for two inorder     # traversals      s1 = []     s2 = []        while 1:                    # append the Nodes of first          # tree in stack s1          if root1:             s1.append(root1)             root1 = root1.left            # append the Nodes of second tree         # in stack s2          elif root2:             s2.append(root2)             root2 = root2.left            # Both root1 and root2 are NULL here          elif len(s1) != 0 and len(s2) != 0:             root1 = s1[-1]              root2 = s2[-1]                 # If current keys in two trees are same              if root1.key == root2.key:                 print(root1.key, end = " ")                 s1.pop(-1)                  s2.pop(-1)                    # move to the inorder successor                  root1 = root1.right                  root2 = root2.right                elif root1.key < root2.key:                                    # If Node of first tree is smaller, than                  # that of second tree, then its obvious                  # that the inorder successors of current                  # Node can have same value as that of the                  # second tree Node. Thus, we pop from s2                  s1.pop(-1)                 root1 = root1.right                     # root2 is set to NULL, because we need                  # new Nodes of tree 1                  root2 = None             elif root1.key > root2.key:                 s2.pop(-1)                 root2 = root2.right                  root1 = None            # Both roots and both stacks are empty          else:             break    # A utility function to do inorder traversal  def inorder(root):     if root:         inorder(root.left)          print(root.key, end = " ")         inorder(root.right)    # 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    # Driver Code  if __name__ == '__main__':            # Create first tree as shown in example      root1 = None     root1 = insert(root1, 5)      root1 = insert(root1, 1)      root1 = insert(root1, 10)      root1 = insert(root1, 0)      root1 = insert(root1, 4)      root1 = insert(root1, 7)      root1 = insert(root1, 9)         # Create second tree as shown in example      root2 = None     root2 = insert(root2, 10)      root2 = insert(root2, 7)      root2 = insert(root2, 20)      root2 = insert(root2, 4)      root2 = insert(root2, 9)        print("Tree 1 : ")      inorder(root1)      print()            print("Tree 2 : ")     inorder(root2)     print()        print("Common Nodes: ")      printCommon(root1, root2)        # This code is contributed by PranchalK

C#

using System; using System.Collections.Generic;    // C# program of iterative traversal based method to  // find common elements in two BSTs.  public class GfG {    // A BST node  public class Node {     public int key;     public Node left, right; }    // A utility function to create a new node  public static Node newNode(int ele) {     Node temp = new Node();     temp.key = ele;     temp.left = null;     temp.right = null;     return temp; }    // Function two print common elements in given two trees  public static void printCommon(Node root1, Node root2) {     Stack<Node> s1 = new Stack<Node>();     Stack<Node> s2 = new Stack<Node>();        while (true)     {         // push the Nodes of first tree in stack s1          if (root1 != null)         {             s1.Push(root1);             root1 = root1.left;         }            // push the Nodes of second tree in stack s2          else if (root2 != null)         {             s2.Push(root2);             root2 = root2.left;         }            // Both root1 and root2 are NULL here          else if (s1.Count > 0 && s2.Count > 0)         {             root1 = s1.Peek();             root2 = s2.Peek();                // If current keys in two trees are same              if (root1.key == root2.key)             {                 Console.Write(root1.key + " ");                 s1.Pop();                 s2.Pop();                    // move to the inorder successor                  root1 = root1.right;                 root2 = root2.right;             }                else if (root1.key < root2.key)             {                 // If Node of first tree is smaller, than that of                  // second tree, then its obvious that the inorder                  // successors of current Node can have same value                  // as that of the second tree Node. Thus, we pop                  // from s2                  s1.Pop();                 root1 = root1.right;                    // root2 is set to NULL, because we need                  // new Nodes of tree 1                  root2 = null;             }             else if (root1.key > root2.key)             {                 s2.Pop();                 root2 = root2.right;                 root1 = null;             }         }            // Both roots and both stacks are empty          else         {             break;         }     } }    // A utility function to do inorder traversal  public static void inorder(Node root) {     if (root != null)     {         inorder(root.left);         Console.Write(root.key + " ");         inorder(root.right);     } }    /* A utility function to insert a new Node with given key in BST */ public 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; }    // Driver program  public static void Main(string[] args) {     // Create first tree as shown in example      Node root1 = null;     root1 = insert(root1, 5);     root1 = insert(root1, 1);     root1 = insert(root1, 10);     root1 = insert(root1, 0);     root1 = insert(root1, 4);     root1 = insert(root1, 7);     root1 = insert(root1, 9);        // Create second tree as shown in example      Node root2 = null;     root2 = insert(root2, 10);     root2 = insert(root2, 7);     root2 = insert(root2, 20);     root2 = insert(root2, 4);     root2 = insert(root2, 9);        Console.Write("Tree 1 : " + "\n");      inorder(root1);      Console.WriteLine();      Console.Write("Tree 2 : " + "\n");      inorder(root2);      Console.WriteLine();      Console.Write("Common Nodes: " + "\n");         printCommon(root1, root2);    } }    // This code is contributed by Shrikant13

Producción:

4 7 9 10

Este artículo es una contribución de Ekta Goel . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.