Print Story [RFH] Recursion
Puzzles & Riddles
By veldmon (Thu May 11, 2006 at 06:51:19 AM EST) professor, recursion, depth, breadth, help, communists, communism (all tags)
(Forgive the 2nd post in a day)
My professor says it's possible to do a breadth first tree traversal using the "list of children" approach, but I'm only able to do it with the "next sibling, next child" approach. Could any of you Husians (including communists) assist in completing f2 below? TIA


f1(node)
{
    # depth first
    list_of_children = node->children

    for child in list_of_children {
        f1(child)
    }
}

f2(node)
{
    # breadth first
    list_of_children = node->children

    ???
}

f3(node)
{
    # depth first
    if(node->child) {
        f3(node->child)
    }
    if(node->sibling) {
        f3(node->sibling)
    }
}

f4(node)
{
    # breadth first
    if(node->sibling) {
        f4(node->sibling)
    }
    if(node->child) {
        f4(node->child)
    }
}

< Ask Husi | BBC White season: 'Rivers of Blood' >
[RFH] Recursion | 9 comments (9 topical, 0 hidden) | Trackback
I'm not sure how this impacts our customers by georgeha (4.00 / 3) #1 Thu May 11, 2006 at 06:58:50 AM EST
so I can't assign the proper priority to have a developer look into this.


Rates start at by Breaker (4.00 / 2) #2 Thu May 11, 2006 at 07:05:56 AM EST
1000 GBP per day for my time, discount available for > 2 week booking.

Although, for free, if you're having to walk a tree breadth first I'd examine your data model before writing code.


use python! by ucblockhead (4.00 / 4) #3 Thu May 11, 2006 at 07:06:27 AM EST
Then it's trivial!
---
[ucblockhead is] useless and subhuman
In order to understand recursion by DesiredUsername (4.00 / 4) #4 Thu May 11, 2006 at 07:08:15 AM EST
You must first understand recursion

---
Now accepting suggestions for a new sigline
with regard to the poll by lm (4.00 / 2) #5 Thu May 11, 2006 at 07:11:12 AM EST
If matter is finite, all creation necessarily begins with destruction. Consequently, there is no choice but to destroy because material beings must create to exist.

There is no more degenerate kind of state than that in which the richest are supposed to be the best.
Cicero, The Republic
but is it not written by martingale (4.00 / 1) #9 Thu May 11, 2006 at 04:42:37 PM EST
in Lavoisier 3:16

"Rien ne se perd, rien ne se crée, tout se transforme." (Nothing is destroyed and nothing is created, everything transforms).
--
$E(X_t|F_s) = X_s,\quad t > s$

[ Parent ]
breadth first?!?! by TPD (4.00 / 3) #6 Thu May 11, 2006 at 07:28:57 AM EST
But surely it's closer to tea time!

why sit, when you can sit and swivel with The Ab-SwivellerTM
Your problem is that by ObviousTroll (4.00 / 2) #7 Thu May 11, 2006 at 07:51:34 AM EST
All your functions are missing the "operation" part of the traversal.

Nobody traverses a tree without doing something at each node they visit.

Here's a hint:

visit(node)
{
    #Hellllllooooooo Node!

    #actual work goes here
}

f1(node)
{
    # depth first
    list_of_children = node->children

    for child in list_of_children {
        f1(child)
    }

    visit(node)
}

A breadth first version of this isn't much more subtle, but it requires handling the "visit" part differently and at a different time.

--
You're no good to me dead. Even half-alive would be socially awkward. - Hugh MacLeod

I don't think your f4 is right by jacob (4.00 / 1) #8 Thu May 11, 2006 at 08:08:37 AM EST
Though you didn't explain exactly how you're representing trees. But I think it will definitely fail for, e.g., a balanced binary tree with height 3.

--

[RFH] Recursion | 9 comments (9 topical, 0 hidden) | Trackback