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

## All 3 Replies

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;
}
``````

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;
}
``````

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)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.