Binary search tree iterator implementation with no use of collection classes

Question

I am having trouble figuring out how to implement a binary search iterator. My question is how do i implement an Iterator traversing "in order" while not using the collection classes?

Well the thing is that i have not a clue about how to add "parent" because i find the first 4 items in the iterator when going down but i dont seem to be able to go up since the "parent" either throws nullpointer or dont get the right items.

so how do i add "parent"?

    void add(String string) {
    if (string.compareTo(value) < 0) {
            if(left.left == null){
                left.parent = left;
            }
            if (left == null) {
                size++;

                left = new Node(string);
            if...

thanks.

Answer 1

I suggest a three classes design:

• BinarySearchTree: Public class, It represent a Binary search Tree. It contains the tree root as BinaryTreeNode.
• BinaryTreeNode: Private nested class, It represent a Node, It has the key and the references: to children and to Its parent.

• BinarySearchTreeIterator: Private nested class, It represent an iterator, It use a reference to a BinaryTreeNode to know the current element.

  public class BinarySearchTree implements Iterable<String> {
  
      private BinaryTreeNode root = null;
      private int elements;
  
      @Override
      public Iterator<String> iterator() {
          return new BinarySearchTreeIterator(root);
      }
  
      private static class BinarySearchTreeIterator implements Iterator<String> {
  
          private BinaryTreeNode node;
  
          public BinarySearchTreeIterator(BinaryTreeNode node) {
              if (node != null) {
                  this.node = smallest(node);
              } else {
                  this.node = node;
              }
          }
  
          @Override
          public boolean hasNext() {
              return node != null;
          }
  
          private static BinaryTreeNode smallest(BinaryTreeNode n) {
              if (n.left != null) {
                  return smallest(n.left);
              } else {
                  return n;
              }
          }
  
          @Override
          public String next() {
              String result = node.key;
              if (node.right != null) {
                  node = smallest(node.right);
              } else {
                  while (node.parent != null && node.parent.left != node) {
                      node = node.parent;
                  }
                  node = node.parent;
              }
              return result;
          }
      }
  
      private static class BinaryTreeNode {
  
          private String key;
          private BinaryTreeNode parent;
          private BinaryTreeNode left;
          private BinaryTreeNode right;
  
          public BinaryTreeNode(String key) {
              this.key = key;
          }
      }
  
      public boolean insert(String key) {
          if (key == null) {
              return false;
          }
          int lastElements = elements;
          this.root = insert(key, root, null);
          return lastElements < elements;
      }
  
      private BinaryTreeNode insert(String key, BinaryTreeNode node, BinaryTreeNode parent) {
          BinaryTreeNode result = node;
          if (node == null) {
              result = new BinaryTreeNode(key);
              result.parent = parent;
              this.elements++;
          } else {
              int compare = key.compareTo(node.key);
              if (compare < 0) {
                  result.left = insert(key, node.left, node);
              } else if (compare > 0) {
                  result.right = insert(key, node.right, node);
              }
          }
          return result;
      }
  
      public static void main(String[] args) {
          BinarySearchTree tree = new BinarySearchTree();
          String[] strings = {"l", "f", "t", "c", "g", "p", "u"};
          for (String string : strings) {
              System.out.println("insert: '" + string + "' " + tree.insert(string));
          }
          System.out.println("--");
  
          for (String s : tree) {
              System.out.println(s);
          }
      }
  }
  

It prints:

insert: 'l' true
insert: 'f' true
insert: 't' true
insert: 'c' true
insert: 'g' true
insert: 'p' true
insert: 'u' true
--
c
f
g
l
p
t
u