2

Need to get the leaf node that has minimum depth. I cannot think of a good way to do it without storing additional information in each node, please suggest, thanks very much.

Shang Wang
  • 24,909
  • 20
  • 73
  • 94

2 Answers2

1

The brute force solution is a breadth-first search terminating at the first leaf found, this will be easier to implement iteratively than recursively.

See for instance the pseudo-code in my answer to "Breadth First Vs Depth First" just add another condition to the while-loop.

BTW--This will get you a leaf with the minimum depth, as there may be more than one at that depth. Getting the full set of minimum depth leaves is a little harder. I guess go with an iterative deepening strategy.

Finding out what level that node is one.

Three choices:

Find the node first and the search down the tree for it. It sounds wasteful, but that second search requires visiting only as many nodes as the level, so it really is fast.

Alternately you can keep track as you go. You use three counters levelCounter, thisLevelCounter and nextLevelCounter. Every time you more to a new node you decrement thisLevelCounter, and when it hits zero you've moved down a level so do

levelCounter++
thisLevelCounter = nextLevelCounter
nextLevelCounter = 0

Every time you add a child node to the search list, increment nextLevelCounter. Every time you store a new child node increment nextLevelCounter

Finally, the iterative deepening strategy gives you the sucess level for free (which iteration finds it...) and has the same order of performance (though a slightly higher multiplier) as the breadth first search.

Community
  • 1
  • 1
dmckee --- ex-moderator kitten
  • 98,632
  • 24
  • 142
  • 234
  • I wouldn't even call this brute force. If you want to find the leaf with minimum depth without adding information, this is how you would do it. – drdwilcox Nov 04 '11 at 00:08
  • I thought about bfs, but I don't know how to count depth information? – Shang Wang Nov 04 '11 at 00:08
  • You want to find the *depth* of the shallowest leaf. Oh, that's a different problem. Let's see, you can count the number of level one nodes you insert (the number of children of the root node), and when you start processing those count the number of level two nodes you insert. By induction you can always known how many nodes until you move down a level, so keep track as you go. Of course you have a search tree, so once you find the node you could just count the levels in O(# of levels) time, by searching down the tree for the node you just found---which is simpler. – dmckee --- ex-moderator kitten Nov 04 '11 at 00:17
0

Here code version (hope I didn't miss any error check):

void min_leaf(node_t *t, int *min, int lev, node_t **n) {
    if (!t) {
            return;
    }   

    if (lev > *min) {
            printf("Back from %d at lev %d, min: %d already found\n",
                            t->key,
                            lev,
                            *min);
            return;
    }   

    if (!t->left && !t->right) {
            if (*min > lev) {
                    *min = lev;
                    *n = t;
            }   
    } else {
            min_leaf(t->left, min, lev+1, n); 
            min_leaf(t->right, min, lev+1, n); 
    }   
}

void bst_print_min_leaf(bst_t* bst) {
    int min = 10000; /* Replace it with some really large number */
    node_t *minn = NULL;

    min_leaf(bst->root, &min, 0, &minn); /*level: root is level 0 */
    if (minn) printf("min leaf is at depth: %d: (%p:%d)\n", min, minn, minn->key);
}
bladeWalker
  • 978
  • 1
  • 13
  • 30