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 .


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 += 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;
        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)