Tree search function

Question

Any node can have any number of children. To search this tree i wrote something like this

function Search(key, nodes){

 for (var i = 0; i < nodes.length; i++) {


        if (nodes[i].key == key) {
            return nodes[i];
        }



        if (nodes[i].hasOwnProperty('children')) {
            return this.Search(key, nodes[i].children);
        }


    }

which doesn't quite work...any input?

Answer 1

You only recursively search the first node that has children.

You should rewrite that last conditional to something like this:

if (nodes[i].hasOwnProperty('children')) {
    var node = this.Search(key, nodes[i].children);
    if(node != null)
        return node;
}

You also need to add a case for if the node is not found - for example, a return null at the very bottom of the function.

Answer 2

You seem to be missing a base case. What happens when you encounter a node that has no children and also is not the node you're looking for?

Answer 3

If this is Javascript, this in your code this.Search is probably what's giving you the problem. this means "the current Function object." Try replacing this.Search with just Search.