Reputation: 23
Does anyone know how to traverse a binary search tree using loops instead of recursion?
I have the recursive method
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;
}
Upvotes: 2
Views: 2103
Reputation: 21
A simple approach would be to use a List that runs through it either dept of breadth first.
public static int countMatches(BinaryNodeInterface<Integer> tree, Integer key)
{
ArrayList<Node> open = new ArrayList<Node>();
open.add(tree.getRoot());
int matches = 0;
while(!open.isEmpty())
{
if(open.get(0).hasLeft())
open.add(open.get(0).getLeftChild());
if(open.get(0).hasRight())
open.add(open.get(0).getRightChild());
if(open.get(0).equals(key))
++matches;
open.remove(0);
}
return matches;
}
This is probably not the most efficient way of doing it but it should work for what your asking. This one works depth first but it shouldn't be too hard for you to change it to breadth first if you need.
Upvotes: 0
Reputation: 71
You can use do a level order traversal using a queue
public static int countMatches(BinaryNodeInterface<Integer> tree, Integer key)
{
int matches = 0;
if (tree == null) return 0;
Queue<BinaryTreeNodeInterface<Integer>> queue = new LinkedList<BinaryTreeNodeInterface<Integer>>();
queue.add(tree);
while (!queue.isEmpty()) {
BinaryTreeNodeInterface<Integer> current = queue.remove();
if (current.getData().equals(key))
matches++;
if (current.getLeftChild() != null)
queue.add(current.getLeftChild());
if (current.getRightChild() != null)
queue.add(current.getRightChild());
}
return matches;
}
Upvotes: 1