Loop through binary search tree

[infiniteloop56]

Hi guys,

I have some what of a quick/dumb question. How would one traverse a binary search tree using a loop instead of recursion (An algorithm would be vwry useful if possible)?

I appreciate any help .

Thanks

[infiniteloop56]

This is the recursive version

public static int countMatches(BinaryNodeInterface<Integer> tree,
Integer key)
{
int matches = 0;
if (tree != null)
{
if (tree.getData().equals(key))
matches++;
matches += countMatches(tree.getLeftChild(), key);
matches += countMatches(tree.getRightChild(), key);
}
return matches;
}

[cool_zephyr]

suppose the data struture is like this

public class Node {
    public int data;
    public Node left;
    public Node right;
}





int searchData = 569;
Node node = rootNode; //point to the root node of the binary tree

then the loop would look something like this:

while(node.left != null && node.right != null) {
    if(node.data == searchData)
        break; //data found on this node
    else if(node.data < searchData) 
        node = node.left;
    else 
        node = node.right;
}

[JamesCherrill]

I think that algorithm will fail if there are both left and right nodes - it will just traverse the left-most children.
I think you do need recursion (or something equivalent to recursion)