CODEWITHSUNDEEP
javatree
krystah
krystah

Reputation: 3733

Why is my Binary Tree iterator coming to a halt?

While attempting to traverse a binary-tree in an inorder fashion, it prints the root, the rightmost children and then stops. Something is clearly wrong, and I am having difficulties wrapping my head around this, as I am new to Tree-structures. What am I doing wrong?

Main:

while (tree.iterator().hasNext())
    System.out.println(tree.iterator().next());

Iterator:

public Iterator<T> iterator() {
  Iterator<T> it = new Iterator<T>() {

    Node<T> next = root;

    @Override
    public boolean hasNext() {
      return next != null;
    }

    @Override
    public T next() {
      if (!hasNext())
        throw new NoSuchElementException();

      System.out.println("Returning data");
      T r = next.data;

      if (next.right != null) {
        next = next.right;
        while (next.left != null)
          next = next.left;

      } else while (true) {
        if (next.parent == null) {
          next = null;
          return r;
        }
        if (next.parent.left == next) {
          next = next.parent;
          return r;
        }
        next = next.parent;
      }
      return r;
    }

    @Override
    public void remove() {
      // TODO Auto-generated method stub
    }

  };
  return it;
}

Output:

242
275
279
283

242 is the root of the tree.
242.left = 33
242.right = 283

Update 1:

Tree:

242
|33
||29
|||25
||||NULL
||||NULL
|||NULL
||74
|||70
||||66
|||||NULL
|||||NULL
||||NULL
|||115
||||111
|||||107
||||||NULL
||||||NULL
|||||NULL
||||156
|||||152
||||||148
|||||||NULL
|||||||NULL
||||||NULL
|||||197
||||||193
|||||||NULL
|||||||NULL
||||||238
|||||||234
||||||||NULL
||||||||NULL
|||||||NULL
|283
||279
|||275
||||NULL
||||NULL
|||NULL
||NULL

Upvotes: 1

Views: 62

Answers (1)

Joffrey
Joffrey

Reputation: 37730

You seem to start on the right side of the root, before going to the left-most child. So you miss the whole left part to start with.

You should initialize next with the left-most child, not the root.

Update: You can do that in an initialization block, like this:

Iterator<T> it = new Iterator<T>() {

    Node<T> next;

    {
        next = root;
        while (next.left != null)
            next = next.left;
    }

    @Override
    public boolean hasNext() {
        return next != null;     
    }

    //...
}

Upvotes: 2

Related Questions