Calculating longest path

Question

I have a n-ary tree which contains key values (integers) in each node. I would like to calculate the minimum depth of the tree. Here is what I have come up with so far:

int min = 0;
private int getMinDepth(Node node, int counter, int temp){
    if(node == null){
        //if it is the first branch record min
        //otherwise compare min to this value
        //and record the minimum value
        if(counter == 0){
        temp = min;     
        }else{
        temp = Math.min(temp, min);
        min = 0;
        }
        counter++;//counter should increment by 1 when at end of branch
        return temp;
    }   
    min++;        
    getMinDepth(node.q1, counter, min);
    getMinDepth(node.q2, counter, min);
    getMinDepth(node.q3, counter, min);
    getMinDepth(node.q4, counter, min);
    return temp;
}

The code is called like so:

int minDepth = getMinDepth(root, 0, 0);

The idea is that if the tree is traversing down the first branch (branch number is tracked by counter), then we set the temp holder to store this branch depth. From then on, compare the next branch length and if it smaller, then make temp = that length. For some reason counter is not incrementing at all and always staying at zero. Anyone know what I am doing wrong?

Answer 1

You are passing the counter variable by value, not by reference. Thus, any changes made to it are local to the current stack frame and are lost as soon as the function returns and that frame is popped of the stack. Java doesn't support passing primitives (or anything really) by reference, so you'd either have to pass it as a single element array or wrap it in an object to get the behavior you're looking for.

Here's a simpler (untested) version that avoids the need to pass a variable by reference:

private int getMinDepth(QuadTreeNode node){
    if(node == null)
        return 0;
    return 1 + Math.min(
            Math.min(getMinDepth(node.q1), getMinDepth(node.q2)),
            Math.min(getMinDepth(node.q3), getMinDepth(node.q4)));
}

Both your version and the one above are inefficient because they search the entire tree, when really you only need to search down to the shallowest depth. To do it efficiently, use a queue to do a breadth-first search like Tom recommended. Note however, that the trade-off required to get this extra speed is the extra memory used by the queue.

Edit:

I decided to go ahead and write a breadth first search version that doesn't assume you have a class that keeps track of the nodes' depths (like Tom's NodeWithDepth). Once again, I haven't tested it or even compiled it... But I think it should be enough to get you going even if it doesn't work right out of the box. This version should perform faster on large, complex trees, but also uses more memory to store the queue.

private int getMinDepth(QuadTreeNode node){
    // Handle the empty tree case
    if(node == null)
        return 0;

    // Perform a breadth first search for the shallowest null child
    // while keeping track of how deep into the tree we are.
    LinkedList<QuadTreeNode> queue = new LinkedList<QuadTreeNode>();
    queue.addLast(node);
    int currentCountTilNextDepth = 1;
    int nextCountTilNextDepth = 0;
    int depth = 1;
    while(!queue.isEmpty()){
        // Check if we're transitioning to the next depth
        if(currentCountTilNextDepth <= 0){
            currentCountTilNextDepth = nextCountTilNextDepth;
            nextCountTilNextDepth = 0;
            depth++;
        }
        // If this node has a null child, we're done
        QuadTreeNode node = queue.removeFirst();
        if(node.q1 == null || node.q2 == null || node.q3 == null || node.q4 == null)
            break;
        // If it didn't have a null child, add all the children to the queue
        queue.addLast(node.q1);
        queue.addLast(node.q2);
        queue.addLast(node.q3);
        queue.addLast(node.q4);
        // Housekeeping to keep track of when we need to increment our depth
        nextCountTilNextDepth += 4;
        currentCountTilNextDepth--;
    }

    // Return the depth of the shallowest node that had a null child
    return depth;
}

Answer 2

Counter is always staying at zero because primitives in java are called by value. This means if you overwrite the value in a function call the caller won't see the change. Or if you're familiar with C++ notation it's foo(int x) instead of foo(int& x).

One solution would be to use an Integer object since objects are call-by-reference.

Since you're interested in the minimum depth a breadth first solution will work just fine, but you may get memory problems for large trees.

If you assume that the tree may become rather large an IDS solution would be the best. This way you'll get the time complexity of the breadth first variant with the space complexity of a depth first solution.

Here's a small example since IDS isn't as well known as its brethren (though much more useful for serious stuff!). I assume that every node has a list with children for simplicity (and since it's more general).

public static<T> int getMinDepth(Node<T> root) {
    int depth = 0;
    while (!getMinDepth(root, depth)) depth++;
    return depth;
}

private static<T> boolean getMinDepth(Node<T> node, int depth) {
    if (depth == 0) 
        return node.children.isEmpty();
    for (Node<T> child : node.children) 
        if (getMinDepth(child, depth - 1)) return true;
    return false;
}

For a short explanation see http://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search

Answer 3

I think you're better off doing a breadth-first search. Your current implementation tries to be depth-first, which means it could end up exploring the whole tree if the branches happen to be in an awkward order.

To do a breadth-first search, you need a queue (a ArrayDeque is probably the right choice). You'll then need a little class that holds a node and a depth. The algorithm goes a little something like this:

Queue<NodeWithDepth> q = new ArrayDeque<NodeWithDepth>();
q.add(new NodeWithDepth(root, 1));
while (true) {
  NodeWithDepth nwd = q.remove();
  if (hasNoChildren(nwd.node())) return nwd.depth();
  if (nwd.node().q1 != null) q.add(new NodeWithDepth(nwd.node().q1, nwd.depth() + 1));
  if (nwd.node().q2 != null) q.add(new NodeWithDepth(nwd.node().q2, nwd.depth() + 1));
  if (nwd.node().q3 != null) q.add(new NodeWithDepth(nwd.node().q3, nwd.depth() + 1));
  if (nwd.node().q4 != null) q.add(new NodeWithDepth(nwd.node().q4, nwd.depth() + 1));
}

This looks like it uses more memory than a depth-first search, but when you consider that stack frames consume memory, and that this will explore less of the tree than a depth-first search, you'll see that's not the case. Probably.

Anyway, see how you get on with it.