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)

Not enough information. Post the entire recursive search routine. — Jim Garrison
– Jim Garrison, Commented Dec 5, 2009 at 1:18
Not having a description of what you're actually trying to do makes it hard to evaluate what you have written. This looks awfully complex for what is a relatively simple problem, and has some obvious errors. The most important one is that each recursive invocation will create its own copy of searchedNodes and set exactly one element. The tests further down are only looking in the current invocations's searchedNodes and don't see any values set by other invocations. Can you post a description of the objectives? — Jim Garrison
– Jim Garrison, Commented Dec 5, 2009 at 2:27

Stephen C · Accepted Answer · 2009-12-05 07:19:36Z

2

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.

answered Dec 5, 2009 at 7:19

Stephen C

723k95 gold badges849 silver badges1.3k bronze badges

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

Comments

nayakam · Accepted Answer · 2009-12-05 01:33:10Z

0

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

answered Dec 5, 2009 at 1:33

nayakam

4,2717 gold badges44 silver badges64 bronze badges

Comments

µBio · Accepted Answer · 2009-12-05 02:58:37Z

0

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.

answered Dec 5, 2009 at 2:58

µBio

10.8k6 gold badges41 silver badges56 bronze badges

1 Comment

claudio495h Over a year ago

It's weird for me when you write tree traversal algorithms in the form 'printTree(TreeNode);' instead of 'treeNode.print();' or even 'tree.print();'

Collectives™ on Stack Overflow

Binary tree search algorithm errors

3 Answers 3

Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related