I have a function that traverses BST ( binary search tree) in pre-order recursively. The function is as follows:
public Iterable<Key> preOrder()
{
Queue<Key> queue = new Queue<Key>();
preOrder(queue,root);
return queue;
}
//Criação do método para a verificação pretendida. Método recursivo
private void preOrder(Queue<Key> queue,Node node)
{
if(node != null)
{
queue.enqueue(node.key); //Visitar o nó
preOrder(queue,node.left); //Visitar a sub-árvore esquerda
preOrder(queue,node.right); //Visitar a sub-árvore direita
}
}
I'm trying to figure out how to do the iterative version of this function but I can never come to any conclusions. When in this part of the code
preOrder(queue,node.left); //Visitar a sub-árvore esquerda
preOrder(queue,node.right); //Visitar a sub-árvore direita
I try to write something like this:
queue.enqueue(node.left);
queue.enqueue(node.right);
The IDE warns me (with error included) that I'm getting into type conflict.
If someone can help me figure out the resolution of this function iteratively ... I'm starting Java and it's pretty confusing.
IDE ERROR:
'Node can not be converted to Key type'
Node Class
private class Node {
private Key key; // sorted by key
private Value val; // associated data
private Node left, right; // left and right subtrees
private int size; // number of nodes in subtree
public Node(Key key, Value val, int size) {
this.key = key;
this.val = val;
this.size = size;
}
}
Queue class
public class Queue<Item> implements Iterable<Item> {
private Node<Item> first; // beginning of queue
private Node<Item> last; // end of queue
private int n; // number of elements on queue
// helper linked list class
private static class Node<Item> {
private Item item;
private Node<Item> next;
}