I have a binarySearch Tree and I want to create a method assignFirst.
This method should find the node in the tree with the smallest value and update the tree's "first" attribute accordingly.
I have a lot of methods, but I don't want to include all of them in here, since I want to keep it short and simple. Therefore, I will include the class and some features inside that class.
public class BinarySearchTree<E extends Comparable<E>>
{
private BSTNode<E> root; // root of overall tree
private int numElements;
private BSTNode<E> first;
// post: constructs an empty search tree
public BinarySearchTree()
{
this.root = null;
this.numElements = 0;
}
private void assignFirst()
{
if (root.left == null)
{
first.data = root.data;
}
else
{
first.data = root.left.data;
}
}
public class Iterator
{
private BSTNode<E> currentNode;
public Iterator()
{
currentNode = first;
}
public boolean hasNext()
{
return currentNode != null;
}
public E next()
{
E value = currentNode.data;
currentNode = currentNode.next;
return value;
}
}
private static class BSTNode<E>
{
public E data;
public BSTNode<E> left;
public BSTNode<E> right;
public BSTNode<E> parent;
public BSTNode<E> next;
public BSTNode(E data)
{
this(data, null, null, null, null);
}
public BSTNode(E data, BSTNode<E> left, BSTNode<E> right, BSTNode<E> parent, BSTNode<E> next)
{
this.data = data;
this.left = left;
this.right = right;
this.parent = parent;
this.next = next;
}
}
}
I updated my method look like this. I'm still uncertain if this is the correct way of doing it.
private void assignFirst()
{
if (first.left != null)
{
first = first.left;
}
else
{
first = root;
}
}
I figured it out. I wrote it in like this.
private void assignFirst()
{
BSTNode<E> node = root;
while(node.left != null)
{
node = node.left;
}
first = node;
}