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
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
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)