algorithmrecursiondata-structurestreetraversal
Very specific tree traversal method
I've been trying to develop/find a very specific way to traverse a tree structure. I am really only familiar with the 2~3 most often used tree traversal methods, and I don't know enough jargon to effectively search the web, so please forgive me if I'm asking something very obvious or basic.
I have the following tree structure (not necessarily a binary tree):
(source: renebokhorst.com)
Assume I enter the tree at node "AAA". I would want the method to traverse its underlying nodes using a top down method first.
(source: renebokhorst.com)
However after this, I would want the method to move up the tree, and deal with everything top down below it EXCEPT the part it already did before it.
(source: renebokhorst.com)
I want it to keep doing this until it reaches the top node and finishes.
(source: renebokhorst.com)
A very specific requirement is that we cannot "skip" nodes. Entering, or returning into a node has to be done from either it's parent or child. Before entering a node I also register whether the visitor is traversing up or down the tree (this is necessary information for some visitors). I can similarly also raise flags whether we are entering the tree for the first time, or whether we are passing by the entry node again. The visitor may not visit any node twice except for the entry node, which it may pass multiple times as long as the RE_ENTRY flag is raised. Ideally I do not want to keep track of a list of nodes I already passed in the past. Now I have tried a few different approaches
case GLOBAL_SPREAD:
{
if ( pVisitor->LastVisited == NULL )
pVisitor->VisitDirection = ENTRY;
pVisitor->visit(this);
for ( uint32 i(0) ; i < Children.size() ; i += 1 )
{
pVisitor->VisitDirection = DOWN;
Children[i]->Accept(pVisitor);
}
break;
}
This piece of code of course does nothing else than perform a top down traversal of everything below the starting node. The problems arise when I tried to add code that would bump the visitor up the tree and do a top down traversal from there. Calling Parent->Accept(pVisitor) before visiting the children obviously would not produce the desired results. Calling Parent->Accept(pVisitor) after visiting the children would only produce the desired results in the case of the entry node. For every other node it would cause problems.
I was wondering if anybody had any experience with these types of tree traversal methods, and whether I actually have enough information to do this kind of traversal at all. Again it is important that I do not keep track of any lists of previously visited items. At best I can keep track in the function itself which node was previously visited. Perhaps this is a well known and widely documented traversal method that I just don't know the name of.
Thanks in advance!
Solution
This code seems to implement what you request. The key to this working is that visiting the first node (whatever that is) is considered an UP operation. The print_tree() and print_preorder() functions implement a normal preorder traversal of a tree; they're used to show that the data structure is in the correct shape. The dfs_traversal() and dfs_traverse() functions implement your special DFS traversal. The test code tests two specific examples (the AAA and A nodes), and then does an exhaustive check of the traversal from every node in the tree.
Code
#include <stdio.h>
enum { MAX_CHILD = 2 };
enum { UP = 1, DOWN = 2 };
typedef struct Node Node;
struct Node
{
char name[8];
int number;
Node *parent;
Node *child[MAX_CHILD];
};
static Node data[] =
{
{ "A", 0, 0, { &data[ 1], &data[ 2], }, },
{ "AA", -3, &data[0], { &data[ 3], &data[ 4], }, },
{ "AB", +3, &data[0], { &data[ 5], &data[ 6], }, },
{ "AAA", -4, &data[1], { &data[ 7], &data[ 8], }, },
{ "AAB", +4, &data[1], { &data[ 9], &data[10], }, },
{ "ABA", -4, &data[2], { &data[11], &data[12], }, },
{ "ABB", +4, &data[2], { &data[13], &data[14], }, },
{ "AAAA", 0, &data[3], { 0, 0, }, },
{ "AAAB", +5, &data[3], { 0, 0, }, },
{ "AABA", -5, &data[4], { 0, 0, }, },
{ "AABB", +5, &data[4], { 0, 0, }, },
{ "ABAA", -5, &data[5], { 0, 0, }, },
{ "ABAB", +5, &data[5], { 0, 0, }, },
{ "ABBA", -5, &data[6], { 0, 0, }, },
{ "ABBB", +5, &data[6], { 0, 0, }, },
};
enum { NUM_NODES = sizeof(data) / sizeof(data[0]) };
static void visit(Node *node, int up_down)
{
printf("%4s: ", up_down == UP ? "UP" : "DOWN");
printf(" %5s [%2d] N = %p; P = %p\n", node->name, node->number,
(void *)node, (void *)node->parent);
}
static void print_tree(Node *node)
{
if (node != 0)
{
visit(node, DOWN);
for (int i = 0; i < MAX_CHILD; i++)
print_tree(node->child[i]);
}
}
static void print_preorder(const char *tag, Node *node)
{
printf("Tree starting from %s:\n", tag);
print_tree(node);
}
static void dfs_traverse(int up_down, Node *node, Node *skip)
{
if (node != 0 && node != skip)
{
visit(node, up_down);
for (int i = 0; i < MAX_CHILD; i++)
dfs_traverse(DOWN, node->child[i], skip);
if (node->parent != 0 && up_down == UP)
dfs_traverse(UP, node->parent, node);
}
}
static void dfs_traversal(const char *tag, int up_down, Node *node, Node *skip)
{
printf("DFS starting from %s\n", tag);
dfs_traverse(up_down, node, skip);
}
int main(void)
{
Node *aaa = &data[3];
Node *root = &data[0];
print_preorder("root", root);
print_preorder("aaa", aaa);
dfs_traversal("aaa", UP, aaa, 0);
dfs_traversal("root", UP, root, 0);
for (int i = 0; i < NUM_NODES; i++)
dfs_traversal(data[i].name, UP, &data[i], 0);
return 0;
}
Example output
Tree starting from root:
DOWN: A [ 0] N = 0x10dbab040; P = 0x0
DOWN: AA [-3] N = 0x10dbab068; P = 0x10dbab040
DOWN: AAA [-4] N = 0x10dbab0b8; P = 0x10dbab068
DOWN: AAAA [ 0] N = 0x10dbab158; P = 0x10dbab0b8
DOWN: AAAB [ 5] N = 0x10dbab180; P = 0x10dbab0b8
DOWN: AAB [ 4] N = 0x10dbab0e0; P = 0x10dbab068
DOWN: AABA [-5] N = 0x10dbab1a8; P = 0x10dbab0e0
DOWN: AABB [ 5] N = 0x10dbab1d0; P = 0x10dbab0e0
DOWN: AB [ 3] N = 0x10dbab090; P = 0x10dbab040
DOWN: ABA [-4] N = 0x10dbab108; P = 0x10dbab090
DOWN: ABAA [-5] N = 0x10dbab1f8; P = 0x10dbab108
DOWN: ABAB [ 5] N = 0x10dbab220; P = 0x10dbab108
DOWN: ABB [ 4] N = 0x10dbab130; P = 0x10dbab090
DOWN: ABBA [-5] N = 0x10dbab248; P = 0x10dbab130
DOWN: ABBB [ 5] N = 0x10dbab270; P = 0x10dbab130
Tree starting from aaa:
DOWN: AAA [-4] N = 0x10dbab0b8; P = 0x10dbab068
DOWN: AAAA [ 0] N = 0x10dbab158; P = 0x10dbab0b8
DOWN: AAAB [ 5] N = 0x10dbab180; P = 0x10dbab0b8
DFS starting from aaa
UP: AAA [-4] N = 0x10dbab0b8; P = 0x10dbab068
DOWN: AAAA [ 0] N = 0x10dbab158; P = 0x10dbab0b8
DOWN: AAAB [ 5] N = 0x10dbab180; P = 0x10dbab0b8
UP: AA [-3] N = 0x10dbab068; P = 0x10dbab040
DOWN: AAB [ 4] N = 0x10dbab0e0; P = 0x10dbab068
DOWN: AABA [-5] N = 0x10dbab1a8; P = 0x10dbab0e0
DOWN: AABB [ 5] N = 0x10dbab1d0; P = 0x10dbab0e0
UP: A [ 0] N = 0x10dbab040; P = 0x0
DOWN: AB [ 3] N = 0x10dbab090; P = 0x10dbab040
DOWN: ABA [-4] N = 0x10dbab108; P = 0x10dbab090
DOWN: ABAA [-5] N = 0x10dbab1f8; P = 0x10dbab108
DOWN: ABAB [ 5] N = 0x10dbab220; P = 0x10dbab108
DOWN: ABB [ 4] N = 0x10dbab130; P = 0x10dbab090
DOWN: ABBA [-5] N = 0x10dbab248; P = 0x10dbab130
DOWN: ABBB [ 5] N = 0x10dbab270; P = 0x10dbab130
DFS starting from root
UP: A [ 0] N = 0x10dbab040; P = 0x0
DOWN: AA [-3] N = 0x10dbab068; P = 0x10dbab040
DOWN: AAA [-4] N = 0x10dbab0b8; P = 0x10dbab068
DOWN: AAAA [ 0] N = 0x10dbab158; P = 0x10dbab0b8
DOWN: AAAB [ 5] N = 0x10dbab180; P = 0x10dbab0b8
DOWN: AAB [ 4] N = 0x10dbab0e0; P = 0x10dbab068
DOWN: AABA [-5] N = 0x10dbab1a8; P = 0x10dbab0e0
DOWN: AABB [ 5] N = 0x10dbab1d0; P = 0x10dbab0e0
DOWN: AB [ 3] N = 0x10dbab090; P = 0x10dbab040
DOWN: ABA [-4] N = 0x10dbab108; P = 0x10dbab090
DOWN: ABAA [-5] N = 0x10dbab1f8; P = 0x10dbab108
DOWN: ABAB [ 5] N = 0x10dbab220; P = 0x10dbab108
DOWN: ABB [ 4] N = 0x10dbab130; P = 0x10dbab090
DOWN: ABBA [-5] N = 0x10dbab248; P = 0x10dbab130
DOWN: ABBB [ 5] N = 0x10dbab270; P = 0x10dbab130
DFS starting from A
UP: A [ 0] N = 0x10dbab040; P = 0x0
DOWN: AA [-3] N = 0x10dbab068; P = 0x10dbab040
DOWN: AAA [-4] N = 0x10dbab0b8; P = 0x10dbab068
DOWN: AAAA [ 0] N = 0x10dbab158; P = 0x10dbab0b8
DOWN: AAAB [ 5] N = 0x10dbab180; P = 0x10dbab0b8
DOWN: AAB [ 4] N = 0x10dbab0e0; P = 0x10dbab068
DOWN: AABA [-5] N = 0x10dbab1a8; P = 0x10dbab0e0
DOWN: AABB [ 5] N = 0x10dbab1d0; P = 0x10dbab0e0
DOWN: AB [ 3] N = 0x10dbab090; P = 0x10dbab040
DOWN: ABA [-4] N = 0x10dbab108; P = 0x10dbab090
DOWN: ABAA [-5] N = 0x10dbab1f8; P = 0x10dbab108
DOWN: ABAB [ 5] N = 0x10dbab220; P = 0x10dbab108
DOWN: ABB [ 4] N = 0x10dbab130; P = 0x10dbab090
DOWN: ABBA [-5] N = 0x10dbab248; P = 0x10dbab130
DOWN: ABBB [ 5] N = 0x10dbab270; P = 0x10dbab130
DFS starting from AA
UP: AA [-3] N = 0x10dbab068; P = 0x10dbab040
DOWN: AAA [-4] N = 0x10dbab0b8; P = 0x10dbab068
DOWN: AAAA [ 0] N = 0x10dbab158; P = 0x10dbab0b8
DOWN: AAAB [ 5] N = 0x10dbab180; P = 0x10dbab0b8
DOWN: AAB [ 4] N = 0x10dbab0e0; P = 0x10dbab068
DOWN: AABA [-5] N = 0x10dbab1a8; P = 0x10dbab0e0
DOWN: AABB [ 5] N = 0x10dbab1d0; P = 0x10dbab0e0
UP: A [ 0] N = 0x10dbab040; P = 0x0
DOWN: AB [ 3] N = 0x10dbab090; P = 0x10dbab040
DOWN: ABA [-4] N = 0x10dbab108; P = 0x10dbab090
DOWN: ABAA [-5] N = 0x10dbab1f8; P = 0x10dbab108
DOWN: ABAB [ 5] N = 0x10dbab220; P = 0x10dbab108
DOWN: ABB [ 4] N = 0x10dbab130; P = 0x10dbab090
DOWN: ABBA [-5] N = 0x10dbab248; P = 0x10dbab130
DOWN: ABBB [ 5] N = 0x10dbab270; P = 0x10dbab130
DFS starting from AB
UP: AB [ 3] N = 0x10dbab090; P = 0x10dbab040
DOWN: ABA [-4] N = 0x10dbab108; P = 0x10dbab090
DOWN: ABAA [-5] N = 0x10dbab1f8; P = 0x10dbab108
DOWN: ABAB [ 5] N = 0x10dbab220; P = 0x10dbab108
DOWN: ABB [ 4] N = 0x10dbab130; P = 0x10dbab090
DOWN: ABBA [-5] N = 0x10dbab248; P = 0x10dbab130
DOWN: ABBB [ 5] N = 0x10dbab270; P = 0x10dbab130
UP: A [ 0] N = 0x10dbab040; P = 0x0
DOWN: AA [-3] N = 0x10dbab068; P = 0x10dbab040
DOWN: AAA [-4] N = 0x10dbab0b8; P = 0x10dbab068
DOWN: AAAA [ 0] N = 0x10dbab158; P = 0x10dbab0b8
DOWN: AAAB [ 5] N = 0x10dbab180; P = 0x10dbab0b8
DOWN: AAB [ 4] N = 0x10dbab0e0; P = 0x10dbab068
DOWN: AABA [-5] N = 0x10dbab1a8; P = 0x10dbab0e0
DOWN: AABB [ 5] N = 0x10dbab1d0; P = 0x10dbab0e0
DFS starting from AAA
UP: AAA [-4] N = 0x10dbab0b8; P = 0x10dbab068
DOWN: AAAA [ 0] N = 0x10dbab158; P = 0x10dbab0b8
DOWN: AAAB [ 5] N = 0x10dbab180; P = 0x10dbab0b8
UP: AA [-3] N = 0x10dbab068; P = 0x10dbab040
DOWN: AAB [ 4] N = 0x10dbab0e0; P = 0x10dbab068
DOWN: AABA [-5] N = 0x10dbab1a8; P = 0x10dbab0e0
DOWN: AABB [ 5] N = 0x10dbab1d0; P = 0x10dbab0e0
UP: A [ 0] N = 0x10dbab040; P = 0x0
DOWN: AB [ 3] N = 0x10dbab090; P = 0x10dbab040
DOWN: ABA [-4] N = 0x10dbab108; P = 0x10dbab090
DOWN: ABAA [-5] N = 0x10dbab1f8; P = 0x10dbab108
DOWN: ABAB [ 5] N = 0x10dbab220; P = 0x10dbab108
DOWN: ABB [ 4] N = 0x10dbab130; P = 0x10dbab090
DOWN: ABBA [-5] N = 0x10dbab248; P = 0x10dbab130
DOWN: ABBB [ 5] N = 0x10dbab270; P = 0x10dbab130
DFS starting from AAB
UP: AAB [ 4] N = 0x10dbab0e0; P = 0x10dbab068
DOWN: AABA [-5] N = 0x10dbab1a8; P = 0x10dbab0e0
DOWN: AABB [ 5] N = 0x10dbab1d0; P = 0x10dbab0e0
UP: AA [-3] N = 0x10dbab068; P = 0x10dbab040
DOWN: AAA [-4] N = 0x10dbab0b8; P = 0x10dbab068
DOWN: AAAA [ 0] N = 0x10dbab158; P = 0x10dbab0b8
DOWN: AAAB [ 5] N = 0x10dbab180; P = 0x10dbab0b8
UP: A [ 0] N = 0x10dbab040; P = 0x0
DOWN: AB [ 3] N = 0x10dbab090; P = 0x10dbab040
DOWN: ABA [-4] N = 0x10dbab108; P = 0x10dbab090
DOWN: ABAA [-5] N = 0x10dbab1f8; P = 0x10dbab108
DOWN: ABAB [ 5] N = 0x10dbab220; P = 0x10dbab108
DOWN: ABB [ 4] N = 0x10dbab130; P = 0x10dbab090
DOWN: ABBA [-5] N = 0x10dbab248; P = 0x10dbab130
DOWN: ABBB [ 5] N = 0x10dbab270; P = 0x10dbab130
DFS starting from ABA
UP: ABA [-4] N = 0x10dbab108; P = 0x10dbab090
DOWN: ABAA [-5] N = 0x10dbab1f8; P = 0x10dbab108
DOWN: ABAB [ 5] N = 0x10dbab220; P = 0x10dbab108
UP: AB [ 3] N = 0x10dbab090; P = 0x10dbab040
DOWN: ABB [ 4] N = 0x10dbab130; P = 0x10dbab090
DOWN: ABBA [-5] N = 0x10dbab248; P = 0x10dbab130
DOWN: ABBB [ 5] N = 0x10dbab270; P = 0x10dbab130
UP: A [ 0] N = 0x10dbab040; P = 0x0
DOWN: AA [-3] N = 0x10dbab068; P = 0x10dbab040
DOWN: AAA [-4] N = 0x10dbab0b8; P = 0x10dbab068
DOWN: AAAA [ 0] N = 0x10dbab158; P = 0x10dbab0b8
DOWN: AAAB [ 5] N = 0x10dbab180; P = 0x10dbab0b8
DOWN: AAB [ 4] N = 0x10dbab0e0; P = 0x10dbab068
DOWN: AABA [-5] N = 0x10dbab1a8; P = 0x10dbab0e0
DOWN: AABB [ 5] N = 0x10dbab1d0; P = 0x10dbab0e0
DFS starting from ABB
UP: ABB [ 4] N = 0x10dbab130; P = 0x10dbab090
DOWN: ABBA [-5] N = 0x10dbab248; P = 0x10dbab130
DOWN: ABBB [ 5] N = 0x10dbab270; P = 0x10dbab130
UP: AB [ 3] N = 0x10dbab090; P = 0x10dbab040
DOWN: ABA [-4] N = 0x10dbab108; P = 0x10dbab090
DOWN: ABAA [-5] N = 0x10dbab1f8; P = 0x10dbab108
DOWN: ABAB [ 5] N = 0x10dbab220; P = 0x10dbab108
UP: A [ 0] N = 0x10dbab040; P = 0x0
DOWN: AA [-3] N = 0x10dbab068; P = 0x10dbab040
DOWN: AAA [-4] N = 0x10dbab0b8; P = 0x10dbab068
DOWN: AAAA [ 0] N = 0x10dbab158; P = 0x10dbab0b8
DOWN: AAAB [ 5] N = 0x10dbab180; P = 0x10dbab0b8
DOWN: AAB [ 4] N = 0x10dbab0e0; P = 0x10dbab068
DOWN: AABA [-5] N = 0x10dbab1a8; P = 0x10dbab0e0
DOWN: AABB [ 5] N = 0x10dbab1d0; P = 0x10dbab0e0
DFS starting from AAAA
UP: AAAA [ 0] N = 0x10dbab158; P = 0x10dbab0b8
UP: AAA [-4] N = 0x10dbab0b8; P = 0x10dbab068
DOWN: AAAB [ 5] N = 0x10dbab180; P = 0x10dbab0b8
UP: AA [-3] N = 0x10dbab068; P = 0x10dbab040
DOWN: AAB [ 4] N = 0x10dbab0e0; P = 0x10dbab068
DOWN: AABA [-5] N = 0x10dbab1a8; P = 0x10dbab0e0
DOWN: AABB [ 5] N = 0x10dbab1d0; P = 0x10dbab0e0
UP: A [ 0] N = 0x10dbab040; P = 0x0
DOWN: AB [ 3] N = 0x10dbab090; P = 0x10dbab040
DOWN: ABA [-4] N = 0x10dbab108; P = 0x10dbab090
DOWN: ABAA [-5] N = 0x10dbab1f8; P = 0x10dbab108
DOWN: ABAB [ 5] N = 0x10dbab220; P = 0x10dbab108
DOWN: ABB [ 4] N = 0x10dbab130; P = 0x10dbab090
DOWN: ABBA [-5] N = 0x10dbab248; P = 0x10dbab130
DOWN: ABBB [ 5] N = 0x10dbab270; P = 0x10dbab130
DFS starting from AAAB
UP: AAAB [ 5] N = 0x10dbab180; P = 0x10dbab0b8
UP: AAA [-4] N = 0x10dbab0b8; P = 0x10dbab068
DOWN: AAAA [ 0] N = 0x10dbab158; P = 0x10dbab0b8
UP: AA [-3] N = 0x10dbab068; P = 0x10dbab040
DOWN: AAB [ 4] N = 0x10dbab0e0; P = 0x10dbab068
DOWN: AABA [-5] N = 0x10dbab1a8; P = 0x10dbab0e0
DOWN: AABB [ 5] N = 0x10dbab1d0; P = 0x10dbab0e0
UP: A [ 0] N = 0x10dbab040; P = 0x0
DOWN: AB [ 3] N = 0x10dbab090; P = 0x10dbab040
DOWN: ABA [-4] N = 0x10dbab108; P = 0x10dbab090
DOWN: ABAA [-5] N = 0x10dbab1f8; P = 0x10dbab108
DOWN: ABAB [ 5] N = 0x10dbab220; P = 0x10dbab108
DOWN: ABB [ 4] N = 0x10dbab130; P = 0x10dbab090
DOWN: ABBA [-5] N = 0x10dbab248; P = 0x10dbab130
DOWN: ABBB [ 5] N = 0x10dbab270; P = 0x10dbab130
DFS starting from AABA
UP: AABA [-5] N = 0x10dbab1a8; P = 0x10dbab0e0
UP: AAB [ 4] N = 0x10dbab0e0; P = 0x10dbab068
DOWN: AABB [ 5] N = 0x10dbab1d0; P = 0x10dbab0e0
UP: AA [-3] N = 0x10dbab068; P = 0x10dbab040
DOWN: AAA [-4] N = 0x10dbab0b8; P = 0x10dbab068
DOWN: AAAA [ 0] N = 0x10dbab158; P = 0x10dbab0b8
DOWN: AAAB [ 5] N = 0x10dbab180; P = 0x10dbab0b8
UP: A [ 0] N = 0x10dbab040; P = 0x0
DOWN: AB [ 3] N = 0x10dbab090; P = 0x10dbab040
DOWN: ABA [-4] N = 0x10dbab108; P = 0x10dbab090
DOWN: ABAA [-5] N = 0x10dbab1f8; P = 0x10dbab108
DOWN: ABAB [ 5] N = 0x10dbab220; P = 0x10dbab108
DOWN: ABB [ 4] N = 0x10dbab130; P = 0x10dbab090
DOWN: ABBA [-5] N = 0x10dbab248; P = 0x10dbab130
DOWN: ABBB [ 5] N = 0x10dbab270; P = 0x10dbab130
DFS starting from AABB
UP: AABB [ 5] N = 0x10dbab1d0; P = 0x10dbab0e0
UP: AAB [ 4] N = 0x10dbab0e0; P = 0x10dbab068
DOWN: AABA [-5] N = 0x10dbab1a8; P = 0x10dbab0e0
UP: AA [-3] N = 0x10dbab068; P = 0x10dbab040
DOWN: AAA [-4] N = 0x10dbab0b8; P = 0x10dbab068
DOWN: AAAA [ 0] N = 0x10dbab158; P = 0x10dbab0b8
DOWN: AAAB [ 5] N = 0x10dbab180; P = 0x10dbab0b8
UP: A [ 0] N = 0x10dbab040; P = 0x0
DOWN: AB [ 3] N = 0x10dbab090; P = 0x10dbab040
DOWN: ABA [-4] N = 0x10dbab108; P = 0x10dbab090
DOWN: ABAA [-5] N = 0x10dbab1f8; P = 0x10dbab108
DOWN: ABAB [ 5] N = 0x10dbab220; P = 0x10dbab108
DOWN: ABB [ 4] N = 0x10dbab130; P = 0x10dbab090
DOWN: ABBA [-5] N = 0x10dbab248; P = 0x10dbab130
DOWN: ABBB [ 5] N = 0x10dbab270; P = 0x10dbab130
DFS starting from ABAA
UP: ABAA [-5] N = 0x10dbab1f8; P = 0x10dbab108
UP: ABA [-4] N = 0x10dbab108; P = 0x10dbab090
DOWN: ABAB [ 5] N = 0x10dbab220; P = 0x10dbab108
UP: AB [ 3] N = 0x10dbab090; P = 0x10dbab040
DOWN: ABB [ 4] N = 0x10dbab130; P = 0x10dbab090
DOWN: ABBA [-5] N = 0x10dbab248; P = 0x10dbab130
DOWN: ABBB [ 5] N = 0x10dbab270; P = 0x10dbab130
UP: A [ 0] N = 0x10dbab040; P = 0x0
DOWN: AA [-3] N = 0x10dbab068; P = 0x10dbab040
DOWN: AAA [-4] N = 0x10dbab0b8; P = 0x10dbab068
DOWN: AAAA [ 0] N = 0x10dbab158; P = 0x10dbab0b8
DOWN: AAAB [ 5] N = 0x10dbab180; P = 0x10dbab0b8
DOWN: AAB [ 4] N = 0x10dbab0e0; P = 0x10dbab068
DOWN: AABA [-5] N = 0x10dbab1a8; P = 0x10dbab0e0
DOWN: AABB [ 5] N = 0x10dbab1d0; P = 0x10dbab0e0
DFS starting from ABAB
UP: ABAB [ 5] N = 0x10dbab220; P = 0x10dbab108
UP: ABA [-4] N = 0x10dbab108; P = 0x10dbab090
DOWN: ABAA [-5] N = 0x10dbab1f8; P = 0x10dbab108
UP: AB [ 3] N = 0x10dbab090; P = 0x10dbab040
DOWN: ABB [ 4] N = 0x10dbab130; P = 0x10dbab090
DOWN: ABBA [-5] N = 0x10dbab248; P = 0x10dbab130
DOWN: ABBB [ 5] N = 0x10dbab270; P = 0x10dbab130
UP: A [ 0] N = 0x10dbab040; P = 0x0
DOWN: AA [-3] N = 0x10dbab068; P = 0x10dbab040
DOWN: AAA [-4] N = 0x10dbab0b8; P = 0x10dbab068
DOWN: AAAA [ 0] N = 0x10dbab158; P = 0x10dbab0b8
DOWN: AAAB [ 5] N = 0x10dbab180; P = 0x10dbab0b8
DOWN: AAB [ 4] N = 0x10dbab0e0; P = 0x10dbab068
DOWN: AABA [-5] N = 0x10dbab1a8; P = 0x10dbab0e0
DOWN: AABB [ 5] N = 0x10dbab1d0; P = 0x10dbab0e0
DFS starting from ABBA
UP: ABBA [-5] N = 0x10dbab248; P = 0x10dbab130
UP: ABB [ 4] N = 0x10dbab130; P = 0x10dbab090
DOWN: ABBB [ 5] N = 0x10dbab270; P = 0x10dbab130
UP: AB [ 3] N = 0x10dbab090; P = 0x10dbab040
DOWN: ABA [-4] N = 0x10dbab108; P = 0x10dbab090
DOWN: ABAA [-5] N = 0x10dbab1f8; P = 0x10dbab108
DOWN: ABAB [ 5] N = 0x10dbab220; P = 0x10dbab108
UP: A [ 0] N = 0x10dbab040; P = 0x0
DOWN: AA [-3] N = 0x10dbab068; P = 0x10dbab040
DOWN: AAA [-4] N = 0x10dbab0b8; P = 0x10dbab068
DOWN: AAAA [ 0] N = 0x10dbab158; P = 0x10dbab0b8
DOWN: AAAB [ 5] N = 0x10dbab180; P = 0x10dbab0b8
DOWN: AAB [ 4] N = 0x10dbab0e0; P = 0x10dbab068
DOWN: AABA [-5] N = 0x10dbab1a8; P = 0x10dbab0e0
DOWN: AABB [ 5] N = 0x10dbab1d0; P = 0x10dbab0e0
DFS starting from ABBB
UP: ABBB [ 5] N = 0x10dbab270; P = 0x10dbab130
UP: ABB [ 4] N = 0x10dbab130; P = 0x10dbab090
DOWN: ABBA [-5] N = 0x10dbab248; P = 0x10dbab130
UP: AB [ 3] N = 0x10dbab090; P = 0x10dbab040
DOWN: ABA [-4] N = 0x10dbab108; P = 0x10dbab090
DOWN: ABAA [-5] N = 0x10dbab1f8; P = 0x10dbab108
DOWN: ABAB [ 5] N = 0x10dbab220; P = 0x10dbab108
UP: A [ 0] N = 0x10dbab040; P = 0x0
DOWN: AA [-3] N = 0x10dbab068; P = 0x10dbab040
DOWN: AAA [-4] N = 0x10dbab0b8; P = 0x10dbab068
DOWN: AAAA [ 0] N = 0x10dbab158; P = 0x10dbab0b8
DOWN: AAAB [ 5] N = 0x10dbab180; P = 0x10dbab0b8
DOWN: AAB [ 4] N = 0x10dbab0e0; P = 0x10dbab068
DOWN: AABA [-5] N = 0x10dbab1a8; P = 0x10dbab0e0
DOWN: AABB [ 5] N = 0x10dbab1d0; P = 0x10dbab0e0