Depth first search

From: Phil Bewig <pbewig_at_swbell.net>
Date: 17 Feb 2004 12:10:43 -0800
Message-ID: <455f7154.0402171210.388b47f2@posting.google.com>

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 Received on Tue Feb 17 2004 - 14:10:43 CST