title: AVL Tree Traversal, Search problems
body: <p>I am having a few problems in my AVL tree implementation.. The code for all the rotations and the adding all seem to be correct and I dry-run the program to thoroughly check that it is running logically correct. I seem to be having a problem in my tree traversal (in-order) because it only outputs a few integers from the supposed 100. Also the search is always failing, regardless of what I enter. I cannot seem to grasp what is going on but I suspect that it has something to do with a few null pointers. Below is the code for the AVL tree, I am wondering if there's any incorrect code in the AddNode method or the rotation methods but they seem to be fine.. The classes are Node class, AVL class and AVL tree class which is the main class.</p>
  
  <p>Node class</p>
  
  <pre><code>private int data;
  private Node left;
  private Node right;     
  private int height;
  
  public Node(int m) {
      data = m;        
      left = null;
      right = null;
      height = 0;
  }
  
  public void setToleft(Node newleft) {
      left = newleft;
  }
  
  public Node getleftNode() {
      return left;
  }
  
  public void setToright(Node newright) {
      right = newright;
  }
  
  public Node getrightNode() {
      return right;
  }
  
  public int getData() {
      return data;
  }
  
  public int getHeight(){
      return height;
  }
  
  public void setHeight(int height){
      this.height = height;
  }
  </code></pre>
  
  <p>AVL class</p>
  
  <pre><code>public Node root;
  
  public AVL(int root) {
      this.root = new Node(root); // since root presently has no left or right children, height is currently 0
  }
  
  public int Height(Node n) {
  
      if (n == null) { //basis step                 
          return -1;
      } else { //add one for every path 
          if (n.getleftNode() == null &amp;&amp; n.getrightNode() == null) {
              return 0;
          }
          return 1 + Math.max(Height(n.getleftNode()), Height(n.getrightNode()));
      }
  }
  
  public void add(int data) {
      addNode(data, root);
      root.setHeight(Math.max(Height(root.getleftNode()), Height(root.getrightNode())) + 1);
  }
  
  public void addNode(int data, Node n) {
  
      if (data &lt; n.getData()) {
          if (n.getleftNode() == null) {
              n.setToleft(new Node(data));
          } else {
              addNode(data, n.getleftNode());
          }
  
          n.setHeight(Math.max(Height(n.getleftNode()), Height(n.getrightNode())) + 1);
  
          if ((Height(n.getleftNode()) + 1) - (Height(n.getrightNode()) + 1) == Math.abs(2)) {
              if (data &lt; n.getleftNode().getData()) {
                  n = LLRotation(n);
              } else {
                  n = LRRotation(n);
              }
          }
      } else if (data &gt;= n.getData()) {  //&gt;= also caters for duplicates and inserts them infront of same value
          if (n.getrightNode() == null) {
              n.setToright(new Node(data));
          } else {
              addNode(data, n.getrightNode());
          }
  
          n.setHeight(Math.max(Height(n.getleftNode()), Height(n.getrightNode())) + 1);
  
          if ((Height(n.getrightNode()) + 1) - (Height(n.getleftNode()) + 1) == Math.abs(2)) {
              if (data &gt;= n.getrightNode().getData()) {
                  n = RRRotation(n);
              } else {
                  n = RLRotation(n);
              }
          }
      }
  }
  
  public Node LLRotation(Node n) {      //single
  
      Node n1 = n.getleftNode();
      n.setToleft(n1.getrightNode());
      n1.setToright(n);
      n.setHeight(Math.max(Height(n.getleftNode()), Height(n.getrightNode())) + 1);
      n1.setHeight(Math.max(Height(n1.getleftNode()), Height(n)) + 1);
      //compares heights of left and right subtrees and gets max
      //the above source code is of course vital since the node height must be resetted after rotations
      //adding 1 at the end of the last two code lines is important since 
      //initially the height is only calculated from subtrees onwards
      //same for single right rotation below
      return n1;
  }
  
  public Node RRRotation(Node n) {   //single
  
      Node n1 = n.getrightNode();
      n.setToright(n1.getleftNode());
      n1.setToleft(n);
      n.setHeight(Math.max(Height(n.getleftNode()), Height(n.getrightNode())) + 1);
      n1.setHeight(Math.max(Height(n1.getrightNode()), Height(n)) + 1);
  
      return n1;
  }
  
  public Node LRRotation(Node n) {   //double
  
      n.setToleft(RRRotation(n.getleftNode()));
      return LLRotation(n);       
  }
  
  public Node RLRotation(Node n) {   //double
  
      n.setToright(LLRotation(n.getrightNode()));
      return RRRotation(n);         
  }
  
  public void inOrderTraversal(Node n) {
  
      if (n != null) {
          inOrderTraversal(n.getleftNode()); //recursive call to the left subtree
          System.out.println(n.getData()); //line which makes the actual node to display its data
          inOrderTraversal(n.getrightNode()); //recursive call to the right subtree
      }
  
  }
  
  public void traverse() {
      inOrderTraversal(root);   // can be called in main class to automatically traverse tree from its root
  }
  
  public int search(int x) {
      try {
          if (x == root.getData()) { //basis step
              System.out.println("Item found!");
              return x;
          }
          if (x &lt; root.getData()) {
              root = root.getleftNode();
              return search(x);//recursive call
          } else {
              root = root.getrightNode();
              return search(x);//recursive call
          }
      } catch (NullPointerException e) {
          System.out.println ("Search failed!");
          return 0;
      }
  }
  </code></pre>
  
  <p>Main Class</p>
  
  <pre><code>public static void main(String[] args) throws IOException {
  
      Scanner s = new Scanner(System.in);
  
      AVL tree = null;
  
      int choice = 0;
  
      System.out.println("AVL TREE");
  
      System.out.println("\n Choose an option from the menu: ");
      System.out.println("\n\t 1.) Create file of 100 integers");
      System.out.println("\n\t 2.) Create the tree");
      System.out.println("\n\t 3.) In-Order traverse and show tree");
      System.out.println("\n\t 4.) Search for integer");
      System.out.println("\n\t 5.) Quit");
  
      while (choice != 5) {
  
          System.out.print("\nChoice: ");
          choice = s.nextInt();
  
          switch (choice) {
  
              case 1:
                  createFile();
                  break;
  
              case 2:
                  try {
                      FileReader readto = new FileReader("Integers.txt");
                      BufferedReader br = new BufferedReader(readto);
  
                      String line = br.readLine(); //reads text at start of file                        
                      line = br.readLine(); // skipping empty lines                      
                      line = br.readLine();
                      line = br.readLine();
  
                      int root = Integer.parseInt(line);   //extracts first integer from the line
                      System.out.println("Root: " + root);
  
                      tree = new AVL(root);                        
  
                      int x = 0;
                      while (x != 99) {
                          try {
                              line = br.readLine();
                              int next = Integer.parseInt(line);
                              tree.add(next);
                              System.out.println(next);
                              x++;
                          } catch (NumberFormatException e) {
                          };
                      }
                      System.out.println("Tree successfully populated!");
                  } catch (FileNotFoundException e) {
                      System.out.println("ERROR: File not found!");
                  }
                  break;
  
              case 3:
                  System.out.println("In-Order traversel executed. The now balanced tree shall now be printed in");
                  System.out.println("ascending order and also the left and right children of each node shall be printed.\n");
  
                  System.out.println("Traversal: ");
  
                  tree.traverse();
                  break;
  
              case 4: 
                  System.out.print("Please enter the integer to be searched: ");
                  int x = s.nextInt();
  
                  System.out.println(tree.search(x));
                  break;
  
              case 5:
                  System.exit(0);
                  break;
  
              default:
                  System.out.println("ERROR: Choice out of bounds!");
          }
  
      }
  }
  
  static void createFile() throws IOException {
  
      Random r = new Random();
  
      File intfile = new File("Integers.txt");
      FileWriter writeto = new FileWriter("Integers.txt");
      BufferedWriter bw = new BufferedWriter(writeto);
      if (!(intfile.exists())) {
          System.out.println("ERROR: File not found!");
      } else {
  
          bw.write("The following integers are randomly generated");
          bw.newLine();
          bw.write("and will be used to construct the AVL tree:");
          bw.newLine();
          bw.newLine();
  
          int x;
  
          System.out.println("The following random numbers shall be used to build the AVL tree: \n");
  
          for (int i = 0; i &lt; 100; i++) {
              x = r.nextInt(100) + 1;
              bw.write(String.valueOf(x));
              bw.newLine();
              System.out.println(x);
          }
          bw.close();
      }
  
  }
  </code></pre>
  
  <p>The output for the traversal is just the following:</p>
  
  <p>Traversal: 
  44
  53
  54
  54
  77</p>
  
  <p>Suppose that there were 100 integers entered and among them were these. But the output for the traversal was only this.</p>
  
  <p>Output for the search is like this:
  Choice: 4
  Please enter the integer to be searched: 44
  Item found!
  44</p>
  
  <p>Choice: 4
  Please enter the integer to be searched: 100
  Search failed!
  0</p>
  
  <p>100 and 44 were both integers added to the tree, but 44 was found and 100 wasn't.. I don;t understand..</p>
  
  <p>Anyone can guide me to a solution..?</p>
  
  <p>Thanks in advance :)</p>