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

zw324 · Accepted Answer · 2013-05-09 14:10:12Z

2

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.

edited May 9, 2013 at 14:10

answered May 9, 2013 at 14:05

zw324

27.2k16 gold badges88 silver badges119 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Fox Over a year ago

Thanks a lot....Solved my problem..now there seems to be logical error while doing inorder...Now I will look into it .. Thanks!! :)

JB Nizet · Accepted Answer · 2013-05-09 14:06:24Z

0

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.

answered May 9, 2013 at 14:06

JB Nizet

694k94 gold badges1.3k silver badges1.3k bronze badges

Comments

arcy · Accepted Answer · 2013-05-09 14:08:22Z

0

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.

answered May 9, 2013 at 14:08

arcy

13.2k16 gold badges66 silver badges117 bronze badges

2 Comments

Fox Over a year ago

Will I am returning the int part of the node not the node itself..that it why I choose to use Integer..

arcy Over a year ago

Iterator normally proceeds through a collection of a given class; you used to have Node defined, but now you don't. The definition you had showed Node as having state to be a node in a binary tree. I assumed you were iterating through nodes in the tree, which would be a normal use of an iterator. It is less normal to use an iterator on a collection of one class and have it return a different class. You wanted to know about practices that were not standard, so here is one.

nj-ath · Accepted Answer · 2014-11-11 13:52:14Z

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;
}

This uses only next() function and moves to the next in-order element.

Collectives™ on Stack Overflow

Implementing my own tree Iterator in Java

4 Answers 4

1 Comment

Comments

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

Comments

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related