Binary tree search algorithm errors

Question

I have a binary tree that I need to search through. I'm not searching for one specific node of the tree, but rather over every node of the tree to gain information about them. I have a simple recursive search right now, but every time it runs I get a stack overflow error. It's a full binary tree of depth 7...

if (curDepth < 6 && !searchedNodes[curID * 2]) 
 depthSearch(curNode.getRight());
if (curDepth < 6 && !searchedNodes[curID * 2 + 1]) 
        depthSearch(curNode.getLeft());
if (curID != 1 && !searchedNodes[(int) (curID / 2)]) 
 depthSearch(curNode.getParent());

The curID == 1 corresponds to the root node, so I need to check that it's not the parent. The searchedNodes thing is to make sure i don't search the same node twice. Any ideas on how to do this?

edit: here's the entire search method

public void depthSearch(AntTree curNode) {
     boolean[] searchedNodes = new boolean[128];
     if (curNode == null)
      return;
     int curID = curNode.getID();
     searchedNodes[curID] = true;
     if (curNode.getFood() > 0) {
      AntScript.foodLocs[curID] = 1;
     } else {
      Ant6Script.foodLocs[curID] = 0;
     }
     Ant[] ants = curNode.getAnts();
     boolean containsWorker = false, containsSoldier = false;
     if (ants != null) {
      for (int i = 0; i < ants.length; i++) {
       if (ants[i].type().equals("Worker")
       && ants[i].teamID() != AntScript.myTeamID) {
        containsWorker = true;
       } else if (ants[i].type().equals("Soldier")
       && ants[i].teamID() != AntScript.myTeamID) {
        containsSoldier = true;
       } else if (ants[i].type().equals("Queen")
       && ants[i].teamID() != AntScript.myTeamID) {
        AntScript.enemyQueenLoc = curID;
       }
      }
     }
     if (containsWorker)
      AntScript.enemyWorkerLocs[curID] = 1;
     else
      AntScript.enemyWorkerLocs[curID] = 0;
     if (containsSoldier)
      AntScript.enemySoldierLocs[curID] = 1;
     else
      AntScript.enemySoldierLocs[curID] = 0;
     AntScript.viewedNodeLocs[curID] = 1;
     int curDepth = (int) (Math.log(curID) / Math.log(2));
     if (AntScript.viewedNodeLocs[(int) (curID / 2)] == 0
     || (curDepth < 6 && AntScript.viewedNodeLocs[curID * 2 + 1] == 0)
     || (curDepth < 6 && AntScript.viewedNodeLocs[curID * 2] == 0)) {
      if (curDepth < 6
      && AntScript.viewedNodeLocs[curID * 2] == 0
      && !searchedNodes[curID * 2]) {
       depthSearch(curNode.getLeft());
      }
      if (curDepth < 6
      && AntScript.viewedNodeLocs[curID * 2 + 1] == 0
      && !searchedNodes[curID * 2 + 1]) {
       depthSearch(curNode.getRight());
      }
      if (curID != 1
      && AntScript.viewedNodeLocs[(int) (curID / 2)] == 0
      && !searchedNodes[(int) (curID / 2)]) {
       depthSearch(curNode.getParent());
      }
     } else {
      if (curDepth < 6 && !searchedNodes[curID * 2]) {
       depthSearch(curNode.getRight());
      }
      if (curDepth < 6 && !searchedNodes[curID * 2 + 1]) {
       depthSearch(curNode.getLeft());
      }
      if (curID != 1 && !searchedNodes[(int) (curID / 2)]) {
       depthSearch(curNode.getParent());
      }
     }
    }

The purpose of the viewedNodeLocs array is because i have many ants on a board performing a search from different nodes, and it is better to search through a node that hasn't been searched before than one that has been. I can't just do one big search and then be done because my requests for next nodes are supposed to return null after 13 requests from one ant (this whole thing is from an ant AI thing I'm programming for a game)

Answer 1

You can use the tree traversal technique to get get the information about all node. Check here http://en.wikipedia.org/wiki/Pre-order%5Ftraversal.

Answer 2

You need traversal, not search.

for example, some psuedo code

void PrintTree( TreeNode node ){
    if( node == null ) return;
    if( node.Left != null ) PrintTree( node.Left );
    if( node.Right != null ) PrintTree( node.Right );
    Console.Printline( node.Value );
}

If you want to fire off multiple copies of this code for multiple ants and let only one ant touch any single node, you will need multiple threads and a shared data structure with locking etc.

Better for now to just share a "Map" data structure that each gets a reference to that you build by executing a traversal once. After all a tree of depth 7 is only going to have 128 nodes anyways, so it's not much memory or time to traverse. You can always improve it later if you need to, but at least get it working first.

Answer 3

Your data structure is most peculiar. It looks like you have flattened the tree into an array of nodes. It makes your algorithm really difficult to understand, and is almost certainly a bad idea.

Having said that, I suspect that the problem is related to the fact that each recursive call to depthSearch allocates a new searchedNodes array. Like I said, your algorithm is ... hard to understand.

I suggest that you represent your binary tree in the conventional way, with each node having a 'left' and 'right' pointer. Then implement the traversal in the way described in the wikipedia article. Better still, take a look at the Java Collections framework and see if one of the existing List/Set/Map implementations does what you are trying to do.