Implementing my own tree Iterator in Java

Question

I as trying to implement the Iterator interface for tree traversal. I am getting the following error."Incompatible types at for(Integer node : tr )" and "treeIterator.java uses unchecked or unsafe operations." I am unable to fix this error. Can someone point out the problem.

//class to implement the Iterator interace.
class InorderItr implements Iterator {



    public InorderItr(Node root) {
       st = new Stack<Node>();
       this.root = root;
    }

    @Override
    public boolean hasNext() {
        //has Next
    }

    @Override
    public Integer next(){
          //next node
    }

    @Override 
    public void remove(){
        throw new java.lang.UnsupportedOperationException("Remove not supported.");
    }
}

//This class just makes sure that we use the foreach loop.
class InorderTreeIterator implements Iterable {

    Node root = null;

    public InorderTreeIterator(Node root){
        this.root = root;
    }

    @Override
    public Iterator<Integer> iterator(){
        try{
            return new InorderItr(this.root);
        } catch(UnsupportedOperationException e){
            System.out.println(e.getMessage());
            return null;
        }
    }
}


class treeIterator {

    public static void main(String arg[]){
        treeIterator obj = new treeIterator();
        //create tree.
        InorderTreeIterator tr = new InorderTreeIterator(obj.root);
        for(Integer node : tr ){
            System.out.println(node);
        }
    }
}

PS: This is my first try at implementing iterator interface. If there are any standard practices that I am not following please point out.

Thank You

Answer 1

Iterable is a generic interface. That means, unless you give it a type parameter, it will be a raw type, and the underlying data will be treated as Object.

Change this:

class InorderItr implements Iterator
class InorderTreeIterator implements Iterable

to the following:

class InorderItr implements Iterator<Integer>
class InorderTreeIterator implements Iterable<Integer>

This way, it is no longer a raw type (and that get rids of the warnings of unchecked and unsafe operations the compiler gives you currently), and it tells the compiler that the Iterator will have its underlying data type be Integer (since the type parameter in the Iterator interface is its underlying data type), so the type matches.

Answer 2

Iterator is a generic type. If you use the raw Iterator type, the Iterator returns Object, and the loop should be

for (Object node : tr)

You should instead use a type-safe generic Iterator<Integer>:

class InorderItr implements Iterator<Integer> {

...

class InorderTreeIterator implements Iterable<Integer> {

Also, choose better names for your classes. InorderItr should be InOrderIterator. And InorderTreeIterator should be InorderTreeIterable. Don't name "Iterator" what is not an Iterator. Start class names with upper-case letters, and method names with lower-case letters.

Answer 3

Assuming Java 5 or later: Iterator is actually declared as Iterator, where "E" represents the class returned by next() on the Iterator. I think what you want is

InOrderIterator implements Iterator<Node>

and next() should be declared as

public Node next()

I do not understand why you have Integer in your code; you are clearly attempting to iterate over a tree of Node.

Answer 4

In space (kinda) implementation in C++

#include<iostream>
using namespace std;
struct node
{
    node *left;
    node *right;
    node *parent;
    int data;
} ;

class bst
{
public:
    node *root;
    node *currNode;

    bst()
    {
        root=NULL;
        currNode = NULL;
    }
    int isempty() 
    {
        return(root==NULL);
    }
    void insert(int item);
    void inordertrav();
    void inorder(node *);
    int next();
    node *nextNode(node *root);
    void bft();
};
void bst::insert(int item)
{
    node *p=new node;
    node *parent;
    p->data=item;
    p->left=NULL;
    p->right=NULL;
    p->parent = NULL;
    parent=NULL;
    if(isempty())
        root=p;
    else
    {
        node *ptr;
        ptr = root;
        while(ptr!=NULL)
        {
            parent = ptr;
            if(item > ptr->data)        
                ptr = ptr->right;
            else
                ptr=ptr->left;
        }   
        if(item < parent->data)
        {
            parent->left = p;
        }
        else
            parent->right = p;
        p->parent = parent;
    }
}
void bst::inordertrav()
{
    inorder(root);
}
void bst::inorder(node *ptr)
{
    if(ptr!=NULL)
    {
        inorder(ptr->left);
        cout<<"  "<<ptr->data<<"     ";
        inorder(ptr->right);
    }
}

int bst::next()
{
// If currNode is NULL and find the left most node using a while loop.
    if (currNode == NULL)
    {
        cout << "First node data" << endl;
        node *tmp = root;
        while (tmp->left != NULL)
            tmp = tmp->left;

        currNode = tmp;
        return currNode->data;
    }
    cout << endl << "Current Node is - " << currNode->data << endl;
    if (currNode->right)
    {
        node *tmp = currNode->right;
        while (tmp->left) // find the leftmost node for this right subtree in recursive way without recursion
            tmp = tmp->left;
        currNode = tmp;
        return currNode->data;
    }

    if (! currNode->right) // currNode does not have right child
    {
        if ( currNode->parent->left && currNode->data == currNode->parent->left->data) // CurrNode is the left child
        {
            currNode = currNode->parent;
            return currNode->data;
        }
        if (currNode->parent->right && currNode->data == currNode->parent->right->data) //CurrNode is the right child of the parent
        {
            //If the parent of the currNode (which is right child) is also a right child
            //then this currNode is actually a leaf node and it nothing should be returned.
            if (currNode->parent->parent->right && 
                    currNode->parent->parent->right->data == currNode->parent->data)
            {
                cout << "The tree has been travered fully";
                return -1;
            }
            currNode = currNode->parent->parent;
            return currNode->data;
        }
    }
}


int main()
{
    bst b;
    b.insert(52);
    b.insert(25);
    b.insert(50);
    b.insert(40);
    b.insert(45);
    b.insert(20);
    b.insert(75);
    b.insert(65);
    b.insert(78);
    b.insert(23);
    b.insert(15);

    cout << "---- In order traversal using iterator -----" << endl;
    int i;
    do
    {
        i = b.next();   
        cout << " " << i << " ";
    }while (i != -1);
    cout << endl;
    cout<<endl;
}