Traversal of a tree to find a node

algorithm, binary-tree, java, recursion

Solution

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
 }

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 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.

Original source