Re: Depth first search

> I know this sounds silly, but I'm having trouble coding depth-first
> search of a tree.
>
> My programming language is Oracle PL/SQL, and I'm reading a cursor, so
> I only have one record available at a time. The records are presented
> in pre-order, with the root first, then the root's leftmost child, then
> its children and so on recursively, the the root's second leftmost child,
> thens its children and so on recursively, etc. My task is to ensure
> that, at each level of the tree, an amount stored in each node of the
> tree is truly the sum of its children, or report an error if it is not.
> I also check the amount in the leaves of the tree against another table.
>
> Here is my pseudocode:
>
> DECLARE x GLOBAL;
>
> -- main processing code
> FETCH x_cursor INTO x;
> checktree(x.key,x.amt,x.depth);
> END;
>
> PROCEDURE checktree(key,amt,depth)
> sum := amt;
> LOOP FETCH x_cursor INTO x;
> EXIT WHEN endfile(x_cursor)
> OR x.depth <> depth;
> IF isleaf(x)
> THEN assert(x.amt=lookup(x.key),x.key || " fails lookup");
> ELSE checktree(x.key,x.amt,x.depth);
> sum := sum - x.amt;
> assert(sum=0,"summing error in " || key);
>
> Some sample data is shown below. The key field in x_cursor is
> indented to show the tree structure; normally, this indention is
> not present, and I rely on the depth field to follow the levels of
> the tree. Leaves have six-digit keys; nodes have five-digit keys.
> This data is correct, and my program should report no errors.
>
> x_cursor lookup
>
> key amount depth key amount
> 10000 2,660,835 0 100010 267,138
> 10001 355,957 1 100020 88,819
> 100010 267,138 2 100060 246,891
> 100020 88,819 2 100070 35,329
> 11000 374,457 1 111010 39,346
> 11006 246,891 2 112010 52,891
> 110060 246,891 3 130001 65,794
> 110070 35,329 2 130310 168,445
> 11100 39,346 2 130320 368,276
> 111010 39,346 3 130331 154,758
> 11200 52,891 2 130340 178,380
> 112010 52,891 3 130350 92,575
> 13000 1,930,421 1 130501 4,000
> 130001 65,794 2 130511 209,034
> 13030 962,434 2 130520 108,263
> 130310 168,445 3 130531 50,470
> 130320 368,276 3 130550 184,158
> 13033 154,758 3 130560 124,522
> 130331 154,758 4 130571 103,589
> 130340 178,380 3 130900 118,157
> 130350 92,575 3
> 13050 784,036 2
> 130501 4,000 3
> 13051 209,034 3
> 130511 209,034 4
> 130520 108,263 3
> 13053 50,470 3
> 130531 50,470 4
> 130550 184,158 3
> 130560 124,522 3
> 13057 103,589 3
> 130571 103,589 4
> 130900 118,157 2
>
> Tracing with print statements shows that my code fetches too frequently,
> getting out of sync with the running totals. There also seem to be
> problems where the depth decreases by two or more levels. I see what is
> going wrong, I think, but I don't see how to fix it.
>
> I've been chasing this problem for two days, feeling dumber and dumber
> by the minute. Please help!
>
> Phil

Phil,

How do you ensure that the data is fetched in the correct order?

Imho, it would definetely help if you posted real code with create table, insert into statements.

Rene

-- 
  Rene Nyffenegger
  http://www.adp-gmbh.ch