Depth First Search in Binary Trees/Graphs in Java

Question

I have been trying for a while to get this Graph disguised as a Binary Tree working. Currently I'm using a function that passes in the root node and the ID of the node I am looking for. Only problem is that depending on how I code it, one of my sides can never get past 3 nodes long. I'm sure I'm just not doing the recursion correctly. I've been stuck on this all night, and can't get this. I've tried looking at other graphs and trees, to no avail. We aren't using actual vertexes or other graph like properties, but I can't just use if (x <root.getID()) then root.left, because that doesn't hold up since it is still a "graph"

Here is my non working search algorithm that stops working on the right side if I make it a few nodes long. Visited is using the HashSet() class.

private Node dfs(Node x, int id)
{
    if (x==null) //base case. Runs into null link
       return null;
    if(visited.contains(x.getID())) //visited before
       return null;
    visited.add(x.getID()); //don't go below Node again
    if(id==x.getID())
      return x;
    Node rc = dfs(x.getRightChild(), id);
    Node lc = dfs(x.getLeftChild(), id);
    //recursive calls

  if (lc.getID()==id)
      return lc;
  if(rc.getID()==id)
      return rc;
  return null;
}

I have a working code for printing all of the tree, but I can't get it to change for the key comparison in the above code.

private String dfsPrint(Node x) //pass in root at top level
                                //returns a String containing all ID's
{
   if (x==null) //base case. Runs into null link
       return "";
   if(visited.contains(x.getID())) //visited before
       return "";
   visited.add(x.getID()); //don't go below Node again
   String lc = dfsPrint(x.getLeftChild()); //recursive stuffs
   String rc = dfsPrint(x.getRightChild());
   return Integer.toString(x.getID()) + " " + lc + rc;
}

Thank you for any help.

Edit: I suppose I will expand on what I am doing. I have to have a function makeRight or makeLeft that puts in a new node, and then an existing node puts it has its left or right child. Here is that. In it search is the public method that calls the private dfs.

  Node search(int id) // calls private dfsSearch() returns null or a ref to 
                    // a node with ID = id
{
  int ID = id;
  Node x= dfs(root, ID);
  return x;
}


void ML(int x, int y) // ML command
{
visited.clear();
Node temp = new Node(y, null, null);
Node current = search(x);
current.putLeft(temp);

}

void MR(int x, int y)//MR command
{
visited.clear();
Node temp = new Node(y, null, null);
Node current = search(x);
current.putRight(temp);

}

Depending on how I order the recursive functions if statements for lc and rc, a different side of the tree gets recursed back up to the base case, which is what makes me assume the dfs method is what is wrong. Here is the requested node class.

 class Node {
 private int ID; //ID of the Node. Distinct
 private Node leftChild;
 private Node rightChild;

 Node(int identification)//constructor

{
     ID = identification;
}
 Node(int identification, Node lt, Node rt) //constructor

{
 ID = identification;
 leftChild = lt;
 rightChild = rt;

}

int getID()

{
    return ID;
}

Node getLeftChild()
    {
           return leftChild;
    }
Node getRightChild()
{
    return rightChild;
}
void putLeft(Node lt)
{
    leftChild = lt;
}
void putRight (Node rt)
{
    rightChild = rt;
}

}

The recursive logic itself should work just fine, even though your check for lc.getId() == id and co is quite obfuscating. The only return value the function can have is the node with the correct id or null. Your problem seems to be somewhere else. Maybe include your Node class? Also if it's a binary tree (since it has only two children) you wouldn't need the hashmap, but that shouldn't be the problem either - though we'd need the implementation to be sure. — Voo
I edited the original, so just tell me if you need anything else. Once again, thanks for the help. — Scott

alvi alvi · Accepted Answer · 2011-03-04T15:31:12

you could simplify the code. I don't think you need 'id'. how about this?

private dfs(Node x, int id) {
    if (x==null) { //base case. Runs into null link
       return;
    }
    if(visited.contains(x)) { //visited before
       return;
    }
    visited.add(x); //don't go below Node again
    dfs(x.getRightChild());
    dfs(x.getLeftChild());
}

Depth First Search in Binary Trees/Graphs in Java

2 Answers