CODEWITHSUNDEEP
javabinary-search-tree
pyuntae
pyuntae

Reputation: 832

How to find smallest value in a binary search tree?

I have to write a client method that returns a reference to the information in the node with the smallest value in a binary search tree using the codes given.

Here is the ZIP FILE

I have to use this signature of method:

Golfer min(BinarySearchTree tree)

Here's what I have written:

   Golfer min(BinarySearchTree<Golfer> tree)
   {
      int treeSize = tree.reset(BinarySearchTree.INORDER);
      int numNodes = 0;
      for(int count = 1; count <= treeSize; count++)
      {
         if((tree.getNext(BinarySearchTree.INORDER).compareTo(maxValue)) <= 0)
            numNodes = numNodes + 1;
      }
      return numNodes;     
   }

Upvotes: 0

Views: 1263

Answers (1)

abhaybhatia
abhaybhatia

Reputation: 631

I am guessing you are looking for the Golfer with the minimum score

Method 1: O(lg(n)) time because it runs down the left side of the tree

public Golfer min(BinarySearchTree<Golfer> tree) {
    BSTNode<Golfer> node = tree.root;
    if (node == null) {
        return null;
    }
    while (node.getLeft() != null) {
        node = node.getLeft();
    }
    return node.getInfo();
}


Method 2: O(n) time because it runs through all the elements in the tree to create an in order traversal

public Golfer min2(BinarySearchTree<Golfer> tree) {
    int treeSize = tree.reset(BinarySearchTree.INORDER);
    if (treeSize <= 0) {
        return null;
    }
    return tree.getNext(BinarySearchTree.INORDER);
}

Here is some code to test the code above

public static void main(String[] args) {
    BinarySearchTree<Golfer> bst = new BinarySearchTree<Golfer>();
    bst.add(new Golfer("A", 10));
    bst.add(new Golfer("B", 12));
    bst.add(new Golfer("C", 8));
    bst.add(new Golfer("D", 9));
    bst.add(new Golfer("E", 3));

    Golfer min = new Test().min(bst);
    //Golfer min = new Test().min2(bst);
    if (min != null) {
        System.out.println("min name: " + min.name + ", min score: " + min.score);
    } else {
        System.out.println("Empty tree");
    }
}

Output: 

min name: E, min score: 3

Upvotes: 1

Related Questions