Tree Searching

It has been a very long time since I've written anything on here, what with having a baby daughter to look after and spending most lunchtimes keeping fat at bay in the gym (yes I am aware it's 80% diet, trouble is I don't eat enough, post for another time.)

Anyway I have 10 minutes before the end of my lunch break and looking round my desk can see an interesting note on tree searching.

imagine you have a tree of

                  a
                 / \
                b   c
               /\   /\
              d e  f  g
             /\ /\ /\ /\
            h i jk lm n o

I know this diagram is messy but I have 10 minutes and don't want to leave the text editor yet.

Now image the way in which this structure is expressed is as a map for example

a: b, c

would mean a has children b and c, you could then have an algorithm that would expand the first (left most) item in a list and depending on whether the expansion is stored to the left or right would determine if we had a depth first or bredth first search. I remember when I first saw this idea back in the 90's when playing with Haskell (Hugs98 if anyone's interested) and thought it was cool.

lets expand and store at the front, this would give a depth first search, ooh one other thing to note, leaf nodes are sent to the back since there is nothing to expand on.

1. a
2. bc
3. dec
4. hiec
5. iech
6. echi
7. jkchi
8. kchij
9. chijk
10. fghijk
11. lmghijk
12. mghijkl
13. ghijklm
14. nohijklm
15. ohijklmn
16. hijklmno

now if we expand the nodes but store them at the back of the list

1. a
2. bc
3. cde
4. defg
5. efghi
6. fghijk
7. ghijklm
8. hijklmno

no more expansions as we've reached the depth, so in some pseudo code it could be

expand([x:xs]) => expand[x] : expand[xs]

expand([x:xs]) => expand[xs] : expand[x]

it looks so simple :)

anyway back to work.