CODEWITHSUNDEEP
javatreebinary-treebinary-search-treetree-traversal
user3272998
user3272998

Reputation: 23

Traversal of Binary Search Tree via loop instead of Recursion

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

Answers (2)

Archival
Archival

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

Eric
Eric

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

Related Questions