Binary Search Tree - Sort the same BSTree by name or by weight

[Smiles1]

I've tackled a lot so far! I've created methods to delete, get the weight, and sort the tree by name.

My goal is to have my switch criteria change how the tree is sorted, either by weight or by name.
I haven't figured out how to implement it within my switchCriteria() method, so I've been trying to use my addDogObject() method to sort them as they are added to the tree.

When I run my program and enter to sort by weight first, all of my numbers are sorted correctly.
However, if I sort by name first, then sort by weight, all of the weights are ordered incorrectly?

This makes me think that my name sort is incorrect.

How can I reassemble each node in my tree to be sorted by name, and then by weight and vice versa?
Would I need to reset the tree to null each time and then add in the dog objects again?

Is there way to do this without adding all the objects in again and starting from scratch each time?

I'm currently looking through Big Java Late Objects but can't find a solution that makes sense with what I have currently.

App:

import java.util.Scanner;public class App {

    public static void main(String[] args) {
        BSTree dogOTree = new BSTree();
        Scanner scan = new Scanner(System.in);
        System.out.println("Sort by! name || weight ?");
        String criteria = scan.nextLine();
        
        dogOTree.switchSortCriteria(criteria);
        Dog dogO1 = new Dog("Jackson", 65.28);
        Dog dogO2 = new Dog("Tick", 69.88);
        Dog dogO3 = new Dog("Nia", 75.44);
        //Layla is my dog! She was named after the Eric Clapton song.
        Dog dogO4 = new Dog("Layla", 32.02);
        Dog dogO5 = new Dog("Bagel", 21.06);
        Dog dogO6 = new Dog("Milo", 24.73);
        //Populate DogOTree
        dogOTree.addDogObject(dogO1);
        dogOTree.addDogObject(dogO2);
        dogOTree.addDogObject(dogO3);
        dogOTree.addDogObject(dogO4);
        dogOTree.addDogObject(dogO5);
        dogOTree.addDogObject(dogO6);
        dogOTree.addDogInfo("Baconater", 33.44);
        dogOTree.addDogInfo("FoodBurgular", 22.32);
        dogOTree.addDogInfo("SnackSnatcher", 66.92);
        dogOTree.addDogInfo("ActuallyABlowHorn", 88.26);
        dogOTree.addDogInfo("Clifford", 555.02);

        System.out.println("Sorted by" + criteria);
        dogOTree.displayInOrder();
        //Testing .containsDog()
        System.out.println("Exists: " + dogOTree.containsDog("Layla"));
        System.out.println("Exists: " + dogOTree.containsDog("NonexistantDogO"));
        //Delete successful
        //dogOTree.deleteDog(dogO4);
        //System.out.println("List without DogO4, Baconater");
        //dogOTree.displayInOrder();
        //getDogWeight() successful
        System.out.println(dogOTree.getDogWeight("Layla"));
        System.out.println(dogOTree.getDogWeight("Nia"));
        System.out.println(dogOTree.getDogWeight("Clifford"));
        System.out.println(dogOTree.getDogWeight("Jackson"));
        System.out.println(dogOTree.getDogWeight("Non-existantDogO"));
        
        System.out.println("Sort by! name || weight ?");
        criteria = scan.nextLine();

        dogOTree.switchSortCriteria(criteria);
        dogOTree.displayInOrder();   
  
       
        //getDogWeight() successful
        System.out.println(dogOTree.getDogWeight("Layla"));
        System.out.println(dogOTree.getDogWeight("Nia"));
        System.out.println(dogOTree.getDogWeight("Clifford"));
        System.out.println(dogOTree.getDogWeight("Jackson"));
        System.out.println(dogOTree.getDogWeight("Non-existantDogO"));
    }

}

BSTree:

public class BSTree {

    class Node {

        private Dog data;
        private Node leftChild;
        private Node rightChild;

        Node(Dog data) {
            this.data = data;
            this.leftChild = null;
            this.rightChild = null;
        }
    }

    private Node root;
    private Node tempNode;
    private String criteria;

    public BSTree() {
        root = null;
        tempNode = null;
        criteria = "";
    }

    public boolean addDogObject(Dog data) {
        if(criteria.equalsIgnoreCase("weight")) {
        root = addRecursiveByWeight(root, data);
        }
        else if(criteria.equalsIgnoreCase("name")){
        root = addRecursiveByName(root, data);
        }
        return true;
    }
    //Adds a Dog object to the tree.  Returns true on success or false on failure (if Dog with that name already exists).

    public boolean addDogInfo(String name, double weight) {
        return this.addDogObject(new Dog(name, weight));
    }

    private Node addRecursiveByWeight(Node current, Dog data) {
        if (current == null) { // If it's root
            return new Node(data);
        } else if (data.getWeight() < current.data.getWeight()) { //navigate left
            //Vrrooom vrroom go left
            current.leftChild = addRecursiveByWeight(current.leftChild, data);
            return current;
        } else if (data.getWeight() > current.data.getWeight()) {
            current.rightChild = addRecursiveByWeight(current.rightChild, data);
            return current;
        } else {
            return current;
        }
    }

    private Node addRecursiveByName(Node current, Dog data) {
        if (current == null) {
            return new Node(data);
        } else if (data.getName().compareToIgnoreCase(current.data.getName()) < 0) { //navigate left
            //Vrrooom vrroom go left
            current.leftChild = addRecursiveByWeight(current.leftChild, data);
            return current;
        } else if (data.getName().compareToIgnoreCase(current.data.getName()) > 0) {
            current.rightChild = addRecursiveByWeight(current.rightChild, data);
            return current;
        } else {
            return current;
        }
    }

    public void switchSortCriteria(String userCriteria) {
        //Specifies whether your tree is sorted by the dog's name or weight. If the tree contains elements already, 
        //it will re-order those elements using the criteria specified.  The “criteria” parameter may be equal to “name” or “weight”.
//        if(criteria.equalsIgnoreCase("weight")){
//                      ///Silently screaming
//                      
//        }
//        else if(criteria.equalsIgnoreCase("name")){
//                      //Also silently screaming
//        }
          criteria = userCriteria;
    }

    public boolean containsDog(String name) {
        return containsRecursive(root, name);
        //Start at the root and looks for data
    }

    private boolean containsRecursive(Node current, String name) {
        if (current == null) {
            return false;
        }
        if (name.compareToIgnoreCase(current.data.getName()) == 0) {
            tempNode = current;
            return true;
        }

        boolean inLeft = containsRecursive(current.leftChild, name);

        if (!inLeft) {
            return (containsRecursive(current.rightChild, name));
        }
        return true;
    }    /*
    While node is not null 
    recursively traverse left child
    Display node's value
    recursively traverse right child
     */
    public void displayInOrder() {
        inOrderTraversal(root);
    }

    private void inOrderTraversal(Node node) {
        if (node != null) {
            inOrderTraversal(node.leftChild);
            System.out.println(" " + node.data);
            inOrderTraversal(node.rightChild);
        }
    }

    public double getDogWeight(String name) {
        //Returns the weight of the dog with the specified name if it exists in the tree, or returns -1 otherwise.
        if (containsRecursive(root, name) == true) {
            return tempNode.data.getWeight();
        } else {
            return -1;
        }

    }

    public void deleteDog(Dog data) {
        root = deleteRecursive(root, data);
    }

    private Node deleteRecursive(Node current, Dog data) {

        if (current == null) {
            return current;
        }

        if (data.getWeight() < current.data.getWeight()) {
            current.leftChild = deleteRecursive(current.leftChild, data);
        } else if (data.getWeight() > current.data.getWeight()) {
            current.rightChild = deleteRecursive(current.rightChild, data);
        } else {
            if (current.leftChild == null) {
                return current.rightChild;
            } else if (current.rightChild == null) {
                return current.leftChild;
            }

            current.data.setWeight(findMinVal(current.rightChild));
            current.rightChild = deleteRecursive(current.rightChild, current.data);
        }

        return current;
    }

    public double findMinVal(Node current) {
        double min = current.data.getWeight();

        while (current.leftChild != null) {
            min = current.leftChild.data.getWeight();
            current = current.leftChild;
        }
        return min;
    }
}

Dog class:

public class Dog {
    private String name;
    private double weight;

    public Dog(String name, double weight) {
        this.name = name;
        this.weight = weight;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public double getWeight() {
        return weight;
    }

    public void setWeight(double weight) {
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "Dog {" + " name= " + name + ", weight= " + weight;
    }
    
}

Any help, hints or advice is greatly appreciated!

 

[Smiles1]

This is solved! :-)

I transferred all of my data into an ArrayList, reset the tree, and then added the data back into the tree from the ArrayList using whichever criteria.

 

[Jameson]

This is solved! :-)

I transferred all of my data into an ArrayList, reset the tree, and then added the data back into the tree from the ArrayList using whichever criteria.

Hi Smiles!

Sorry we couldn't help you in time, but would you mind posting your solution so another person might benefit from it in the future? :)

 

[johng1]

Smiles,
A binary search tree is a binary tree together with ONE total ordering of the nodes. So with different orders for Dog data, you can't have just one binary search tree. Here's a solution that just adds a field orderByName (specifying the order for this tree) to BSTree; the compareTo method of Node is computed according to this orderByName.

Since you seem to be just now learning about trees, I've included several non-recursive methods in class BSTree. Certainly, recursion is a very good way to implement methods for trees, but I think non-recursive implementation aids the understanding.

public class App {
   public static void main(String[] args) {
      BSTree nameTree = new BSTree(true);
      BSTree weightTree = new BSTree(false);

      nameTree.addDog("Jackson", 65.28);
      nameTree.addDog("Tick", 69.88);
      nameTree.addDog("Nia", 75.44);
      //Layla is my dog! She was named after the Eric Clapton song.
      nameTree.addDog("Layla", 32.02);
      nameTree.addDog("Bagel", 21.06);
      nameTree.addDog("Milo", 24.73);

      nameTree.displayInOrder();

      weightTree.addDog("Jackson", 65.28);
      weightTree.addDog("Tick", 69.88);
      weightTree.addDog("Nia", 75.44);
      //Layla is my dog! She was named after the Eric Clapton song.
      weightTree.addDog("Layla", 32.02);
      weightTree.addDog("Bagel", 21.06);
      weightTree.addDog("Milo", 24.73);

      weightTree.displayInOrder();

   }
   
}

public class BSTree {
   boolean orderedByName;
   BSTree(boolean byName) {
      orderedByName = byName;
      root = null;
   }

   class Node {

      Dog data;
      Node leftChild;
      Node rightChild;

      Node(Dog data) {
         this.data = data;
         this.leftChild = null;
         this.rightChild = null;
      }

      public int compareTo(Dog t) {
         if (orderedByName) {
            return (t.getName().compareToIgnoreCase(data.getName()));
         }
         return ((int) (t.getWeight() - data.getWeight()));
      }

   }

    private Node root;
  
    
   public BSTree() {
      root = null;
   }

   public boolean add(Dog data) {
      if (contains(data)) {
         return (false);
      }
      Node ng = new Node(data);
      root = addRecursive(root, ng);
      return true;
   }
    
   // upon entry, no node of the tree has node.data == data
    private Node addRecursive(Node current, Node toAdd) {
      if (current == null) { // If it's root OR fell off the tree
         return (toAdd);
      } else if (current.compareTo(toAdd.data) < 0) { //navigate left
         //Vrrooom vrroom go left
         current.leftChild = addRecursive(current.leftChild, toAdd);
         return current;
      } else {
         current.rightChild = addRecursive(current.rightChild, toAdd);
         return current;
      }
   }

    
    public void displayInOrder() {
        inOrderTraversal(root);
    }

   private void inOrderTraversal(Node node) {
      if (node != null) {
         inOrderTraversal(node.leftChild);
         System.out.println(" " + node.data);
         inOrderTraversal(node.rightChild);
      }
   }
    //Adds a Dog object to the tree.  Returns true on success or false on failure (if Dog with that name already exists).
   public boolean addDog(String name, double weight) {
      return this.add(new Dog(name, weight));
   }
// returns true iff the tree contains a node with data t
   public boolean contains(Dog t) {
      if (root == null) {
         return (false);
      }
      Node p = root;
      int comp;
      while (p != null) {
         comp = p.compareTo(t);
         if (comp == 0) {
            return (true);
         }
         if (comp < 0) {
            p = p.leftChild;
         } else {
            p = p.rightChild;
         }
      }
      return (false);
   }
   
/* The following are two non-recursive binary tree traversal.  They both use
   a stack data structure.
   */    
   void preTrav() {
      ArrayDeque stk = new ArrayDeque();
      Node p;
      stk.push(root);
      while (!stk.isEmpty()) {
         p = (Node) stk.pop();
         System.out.println(p.data);
         if (p.rightChild != null) {
            stk.push(p.rightChild);
         }
         if (p.leftChild != null) {
            stk.push(p.leftChild);
         }
      }
   }
   
   void inTrav() {
      ArrayDeque stk = new ArrayDeque();
      Node p = root;
      while (true) {
         while (p != null) {
            stk.push(p);
            p = p.leftChild;
         }
         if (stk.isEmpty()) {
            break;
         }
         p = (Node) stk.pop();
         System.out.println(p.data);
         p = p.rightChild;
      }
   }
// Here's a non-recursive method that adds a node with data dg.   
   boolean insert(Dog dg) {
      Node ng = new Node(dg);
      Node p = root, q = null;
      int comp = 0;
      while (p != null) {
         q = p;
         comp = p.compareTo(dg);
         if (comp == 0) {
            return (false);  // already in tree
         }
         if (comp < 0) {
            p = p.leftChild;
         } else {
            p = p.rightChild;
         }
      }
      if (q == null) {
         root = ng;
      } else {
         if (comp < 0) {
            q.leftChild = ng;
         } else {
            q.rightChild = ng;
         }
      }
      return (true);
   }
// Here's the "standard" non-recursive method that deletes THE node with data dg.   
   boolean remove(Dog dg) {
      Node p = root, parentOfP = null, q, parentOfQ;
      int comp;
      boolean leftFromParent = true;
      while (p != null) {
         comp = p.compareTo(dg);
         if (comp == 0) {
            break;
         }
         if (comp < 0) {
            parentOfP = p;
            p = p.leftChild;
         } else {
            parentOfP = p;
            p = p.rightChild;
         }
         leftFromParent = comp < 0;
      }
      if (p == null) { // dg NOT in tree
         return (false);
      }
      if (p.rightChild != null) {
         q = p.rightChild;
         parentOfQ = null;
         while (q.leftChild != null) {
            parentOfQ = q;
            q = q.leftChild;
         }
         if (parentOfQ != null) {
            parentOfQ.leftChild = q.rightChild;
            q.rightChild = p.rightChild;
         }
         q.leftChild = p.leftChild;
      } else {
         q = p.leftChild;
      }
      if (parentOfP == null) {
         root = q;
      } else {
         if (leftFromParent) {
            parentOfP.leftChild = q;
         } else {
            parentOfP.rightChild = q;
         }
      }
      return (true);
   }
}