I am trying to create a class iNode that implements an Iterator to traverse a Binary Search Tree. The Iterator searches in a PreOrder traversal and can pick from any node in a tree, this node has the value of the int value.

I am familiar with using Stacks on BSTs, but am having a bit of trouble with the Iterator's hasNext() and next() methods.

I understand that logically, hasNext must check the current iNode and see if it has children. Then while that is true, the next() function will iterate through the tree starting with the "root" or value, then favoring the left children, and finally the right children. I believe that this is a simple matter of syntax and would greatly appreciate a few tips.

Expected behavior:

should return an Iterable (type Integer) of [8,3,5,6,4,2]

import java.util.Iterator;
import java.util.NoSuchElementException;

public class iNode implements Iterable<Integer> {

    public final Integer value;
    public final iNode left, right;

    public iNode(Integer value) {
        this.value = value;
        this.right = null;
        this.left = null;
        // a node with no children / root
    }

    public iNode(Integer value, iNode left, iNode right) {
        this.value = value;
        this.left = left;
        this.right = right;
        // with children
    }

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {

            private iNode next = new iNode(value, left, right);

            @Override
            public boolean hasNext() {
                // should return false when the current node has no children
                return next != null;
            }

            @Override
            public Integer next() {
                if (!hasNext()) {
                    throw new NoSuchElementException("limit reached");
                }
                return next.value;
            }
        };
    }
}

CodePudding user response：

private static void printPreOrder(Node root) {
    
    if(root == null) {
        return;
    }
    
    System.out.println(root.value   "->");
    
    printPreOrder(root.left);
    printPreOrder(root.right);
    
    
}

Let recursion handle this . Just write a base case where the node is null.

private static void printPreOrder(Node root, List<Integer> list) {
    
    if(root == null) {
        return;
    }
    
    list.add(root.value);
    
    printPreOrder(root.left);
    printPreOrder(root.right);
    
    
}

Iterator<Integer> itr = list.iterator();
while(itr.hasNext()){
    int ele = itr.next();
    // print element
}

if you want to store them and then use a iterator to iterate the list.

CodePudding user response：

You can still use a Stack when using an iterator. Iterators are supposed to have state so that they know at which point they are at.

// to record how deep in the tree we are at
// this stores the next nodes to visit
// obviously, start with the current node, "this"
private final Deque<iNode> stack = new ArrayDeque<>(List.of(iNode.this));

@Override
public boolean hasNext() {
    return !stack.isEmpty(); // has next, iff there are next nodes to visit
}

@Override
public Integer next() {
    // pop will throw NSEE if the stack is empty anyway,
    // so you don't need to explicitly throw one, 
    // unless you want a custom message of course
    iNode node = stack.pop(); // we are going to return the value of this later

    // the next node to visit is the left node, then the right node
    // so we should push the right node first, then the left node,
    // which causes the left node to be popped *first*
    if (node.right != null) stack.push(node.right);
    if (node.left != null) stack.push(node.left);
    return node.value;
}

Example usage:

var tree = new iNode(
    8, new iNode(
        3, new iNode(5), new iNode(6)
    ), new iNode(
        4, null, new iNode(2)
    )
);
for (var i : tree) {
    System.out.println(i);
}
/*
8
3
5
6
4
2
*/