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
– Voo, Commented Mar 4, 2011 at 16:02
I edited the original, so just tell me if you need anything else. Once again, thanks for the help. — Scott
– Scott, Commented Mar 4, 2011 at 16:17

alvi · Accepted Answer · 2011-03-04 15:31:12Z

1

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());
}

answered Mar 4, 2011 at 15:31

alvi

2,7021 gold badge23 silver badges35 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Scott Over a year ago

Well, I'm searching for the node with the ID passed into the method, so if I got rid of the id, I would just be traversing it with no purpose I think

alvi Over a year ago

ok, but then you could just insert: if(id==x.getID()) { return x; }

Scott Over a year ago

The simple way I can get it down to is private Node dfs(Node x, int id) { if (x==null) { //base case. Runs into null link return null; } if(visited.contains(x)) { //visited before return null; } visited.add(x); //don't go below Node again dfs(x.getRightChild(), id); dfs(x.getLeftChild(), id); if (id==x.getID()) return x; return null; this also doesn't work. Am I doing this wrong?

Jaxox Over a year ago

Question: why do you need to check is the node is visited in a binary tree?

alvi Over a year ago

You don't need it. The original code in the question had this check, that's why it's here. Maybe he wants different behavior when it's called the 2nd time?

Dunaril · Accepted Answer · 2011-03-04 15:07:34Z

0

Your dfs method returns null in several cases. When you try to call getId() on such a returned value, you should get an exception. Don't you ?

answered Mar 4, 2011 at 15:07

Dunaril

2,8155 gold badges34 silver badges55 bronze badges

1 Comment

Scott Over a year ago

Yes, that is correct. I get the expected nullPointerException, but I really wasn't sure how to test it otherwise, because the function I am having issues with makes a node, and then sets it as the left or right child of an already existing node. I think I'm just not seeing how the recursion works, because none of the input I'm using should be hitting a null if this works properly. EDIT: I can confirm the null that I am hitting is the one in the base case.

Collectives™ on Stack Overflow

Depth First Search in Binary Trees/Graphs in Java

2 Answers 2

5 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related