Iterador de árbol binario para recorrido en orden

Dado un árbol binario y una array de entrada. La tarea es crear un iterador que utilice las funciones next() y hasNext() para realizar un recorrido en orden en el árbol binario.

Ejemplos:

Entrada:        8                           Array de entrada = [siguiente(), tieneSiguiente(), siguiente(), siguiente(), siguiente(), tieneSiguiente(), siguiente(), siguiente(), tieneSiguiente()]
                / \                
              3 9
           / \                        
        2 4                                       
                 \ 
                  5     

Salida: [2, verdadero, 3, 4, 5, verdadero, 8, 9, falso]         
Explicación: De acuerdo con el orden de recorrido, se calcula la respuesta a la array de entrada. 
Recorrido en orden = {2, 3, 4, 5, 8, 9}

Entrada:     4 Array de entrada = [hasNext(), next(), next(), hasNext()]
            / \
          3 2
                    \
                     1 

Salida: [verdadero, 3, 4 verdadero]           

Enfoque ingenuo: se necesita una forma de volver al ancestro una vez que llegamos al Node hoja del árbol binario. Se puede usar una estructura de datos  Stack para esto.

Algoritmo: 

La clase es instanciada

1. inicializar la pila
2. establecer el Node actual = root
3. mientras que actual! = NULL
   1. agregar corriente a la pila
   2. actual = actual.izquierda

función hasNext()

SI la pila no está vacía

    volver verdadero

MÁS

    falso retorno

función siguiente()

• SI la pila está vacía (o hasNext() devuelve falso)
  • Lanzar una excepción
• MÁS
  • Inicializar actual = stack.top
  • Extrae el elemento de la pila
  • Si actual.correcto != NULL
    • Inicializar siguiente = actual->derecha
    • ¡mientras sigue! = NULL
      • añadir al lado de la pila
      • siguiente = siguiente.izquierda
  • corriente de retorno

A continuación se muestra la implementación del enfoque anterior.

// Java Program for above approach
import java.util.*;
 
// Structure of a Node
class Node {
    int data;
    Node left;
    Node right;
 
    Node(int data)
    {
        this.data = data;
        left = right = null;
    }
}
 
// Inorder Iterator class
class InorderIterator {
    private Stack<Node> traversal;
 
    InorderIterator(Node root)
    {
        traversal = new Stack<Node>();
        moveLeft(root);
    }
 
    private void moveLeft(Node current)
    {
        while (current != null) {
            traversal.push(current);
            current = current.left;
        }
    }
 
    public boolean hasNext()
    {
        return !traversal.isEmpty();
    }
 
    public Node next()
    {
        if (!hasNext())
            throw new NoSuchElementException();
 
        Node current = traversal.pop();
 
        if (current.right != null)
            moveLeft(current.right);
 
        return current;
    }
}
 
// Class to Test given set of inputs
class Test {
 
    // Driver Code
    public static void main(String args[])
    {
        Node root = new Node(8);
        root.right = new Node(9);
        root.left = new Node(3);
        root.left.left = new Node(2);
        root.left.right = new Node(4);
        root.left.right.right = new Node(5);
 
        InorderIterator itr = new InorderIterator(root);
        try {
            System.out.print(itr.next().data + " ");
            System.out.print(itr.hasNext() + " ");
            System.out.print(itr.next().data + " ");
            System.out.print(itr.next().data + " ");
            System.out.print(itr.next().data + " ");
            System.out.print(itr.hasNext() + " ");
            System.out.print(itr.next().data + " ");
            System.out.print(itr.next().data + " ");
            System.out.print(itr.hasNext() + " ");
        }
        catch (NoSuchElementException e) {
            System.out.print("No such element Exists");
        }
    }
}

2 true 3 4 5 true 8 9 false 

Complejidad de tiempo: O(N), donde N es el número de Nodes en el árbol binario. 
Espacio auxiliar: O (N), la pila contendrá todos los elementos N en el peor de los casos.

Enfoque eficiente: Morris Traversal se puede usar para resolver esta pregunta usando un espacio constante. La idea detrás de morris traversal es crear un enlace temporal entre un Node y el Node más a la derecha en su subárbol izquierdo para que el Node antepasado pueda retroceder. Una referencia del Node antepasado se establece en el hijo derecho del Node más a la derecha en su subárbol izquierdo.

Algoritmo: 

La clase es instanciada

Inicializar actual = root y rightMost = NULL

función hasNext()

SI actual != NULL

   volver verdadero

MÁS

   falso retorno

función siguiente()

• IF actual = NULL (o hasNext() devuelve falso)
  • Lanzar una excepción
• MÁS
  • IF actual.izquierda = NULL
    • Inicializar temp = actual
    • actual = actual.derecho
    • temperatura de retorno
  • MÁS
    • Inicializar rightMost = actual->izquierda
    • while rightMost.right != NULL && rightMost.right != actual
      • más a la derecha = más a la derecha. a la derecha
      • IF más a la derecha.derecha == NULL
        • rightMost.right = actual
        • actual = actual.izquierda
      • MÁS
        • temperatura = corriente
        • más a la derecha.derecha = nulo
        • actual = actual.derecho
        • corriente de retorno
      • Vuelve a llamar a la función

A continuación se muestra la implementación del enfoque anterior.

// Java Program for above approach
import java.util.*;
 
// Structure of a Node
class Node {
    int data;
    Node left;
    Node right;
 
    Node(int data)
    {
        this.data = data;
        left = right = null;
    }
}
 
// Inorder Iterator class
class InorderIterator {
    private Node current, rightMost;
 
    InorderIterator(Node root)
    {
        current = root;
        rightMost = null;
    }
 
    public boolean hasNext() { return current != null; }
 
    public Node next()
    {
        if (!hasNext())
            throw new NoSuchElementException();
 
        if (current.left == null) {
            Node temp = current;
            current = current.right;
            return temp;
        }
 
        rightMost = current.left;
 
        while (rightMost.right != null
               && rightMost.right != current)
            rightMost = rightMost.right;
 
        if (rightMost.right == null) {
            rightMost.right = current;
            current = current.left;
        }
 
        else {
            rightMost.right = null;
            Node temp = current;
            current = current.right;
            return temp;
        }
 
        return next();
    }
}
 
class Test {
 
    // Driver Code
    public static void main(String args[])
    {
        Node root = new Node(8);
        root.right = new Node(9);
        root.left = new Node(3);
        root.left.left = new Node(2);
        root.left.right = new Node(4);
        root.left.right.right = new Node(5);
 
        InorderIterator itr = new InorderIterator(root);
        try {
            System.out.print(itr.next().data + " ");
            System.out.print(itr.hasNext() + " ");
            System.out.print(itr.next().data + " ");
            System.out.print(itr.next().data + " ");
            System.out.print(itr.next().data + " ");
            System.out.print(itr.hasNext() + " ");
            System.out.print(itr.next().data + " ");
            System.out.print(itr.next().data + " ");
            System.out.print(itr.hasNext() + " ");
        }
        catch (NoSuchElementException e) {
            System.out.print("No such element Exists");
        }
    }
}

2 true 3 4 5 true 8 9 false 

Complejidad temporal: O(N), donde N es el número de Nodes del árbol binario. Aunque estamos creando enlaces temporales y los Nodes se recorren varias veces (como máximo 3 veces), la complejidad del tiempo sigue siendo lineal.
Espacio Auxiliar: O(1)