Traversal of a tree to find a node

Question

Hi again.... I'm either really stupid or my program hates me. Probably both.

Problem: I am searching through a tree to find a value that is passed. Unfortunately, it does not work. I started debugging it with prints and stuff, and what is weird is it actually finds the value... But skips the return statement!!!

    /**
  * Returns the node with the passed value
  */
 private TreeNode searchNodeBeingDeleted(Comparable c, TreeNode node)
 {  
  if(node == null) 
  {
   return null;
  }

  if(c.equals((Comparable)node.getValue()))
  {
   System.out.println("Here");
   return node;
  }
  else
  {
   if(node.getLeft() != null)
   {
    System.out.println("left");
    searchNodeBeingDeleted(c, node.getLeft());
   }
   if(node.getRight() != null)
   {
    System.out.println("right");
    searchNodeBeingDeleted(c, node.getRight());
   }
  }
  return null; //i think this gives me my null pointer at bottom
 }

It prints out the results as follows:

left
left
right
right
Here
right
left
right
left
right
Exception in thread "main" java.lang.NullPointerException
at Program_14.Driver.main(Driver.java:29)

I dont know if this will help, but here is my tree:

     L
   /   \
  D     R
 / \   / \
A   F M   U
 \       / \
  B     T   V

Thanks for your time :)

Answer 1

I think you must return the value of searchNodeBeingDeleted(c, node.getLeft()) and searchNodeBeingDeleted(c, node.getRight()), not just call those methods.

Answer 2

You are using recursion in your function. The 'here' you see is the result of a function call that has been created from the same function. So it will return a value to the 'recursing' function, at this point you aren't done yet, even though you have found the answer, you still need to keep propagating it upwards.

Answer 3

Try this:

private TreeNode searchNodeBeingDeleted(Comparable c, TreeNode node)
 {  
  if(node == null) 
  {
   return null;
  }

  if(c.equals((Comparable)node.getValue()))
  {
   System.out.println("Here");
   return node;
  }
  else
  {
   if(node.getLeft() != null)
   {
    System.out.println("left");
    TreeNode n = searchNodeBeingDeleted(c, node.getLeft());
    if (n != null) {
      return n;
    }
   }
   if(node.getRight() != null)
   {
    System.out.println("right");
    TreeNode n = searchNodeBeingDeleted(c, node.getRight());
    if (n != null) {
      return n;
    }
   }
  }
  return null; //i think this gives me my null pointer at bottom
 }

Answer 4

Assuming your tree is a binary search tree and not a "regular" binary tree.

You should return your recursive calls and not return null at the end of your method.

Something like this:

private TreeNode searchNodeBeingDeleted(Comparable c, TreeNode node) {
    if(nodle == null) return null;
    int diff = c.compareTo((Comparable)node.getValue());
    if (diff == 0) { // yes, we found a match!
        System.out.println("Here");
        return node;
    }
    else if (diff < 0) { // traverse to the left
        System.out.println("left");
        return searchNodeBeingDeleted(c, node.getLeft());
    }
    else {  // traverse to the right
        System.out.println("right");
        return searchNodeBeingDeleted(c, node.getRight());
    }
}