/* Examines the binary tree rooted at |node|. Zeroes |*okay| if an error occurs. Otherwise, does not modify |*okay|. Sets |*count| to the number of nodes in that tree, including |node| itself if |node != NULL|. Sets |*height| to the tree's height. All the nodes in the tree are verified to be at least |min| but no greater than |max|. */ static void recurse_verify_tree (struct rtavl_node *node, int *okay, size_t *count, int min, int max, int *height) { int d; /* Value of this node's data. */ size_t subcount[2]; /* Number of nodes in subtrees. */ int subheight[2]; /* Heights of subtrees. */ if (node == NULL) { *count = 0; *height = 0; return; } d = *(int *) node->rtavl_data; if (min > max) { printf (" Parents of node %d constrain it to empty range %d...%d.\n", d, min, max); *okay = 0; } else if (d < min || d > max) { printf (" Node %d is not in range %d...%d implied by its parents.\n", d, min, max); *okay = 0; } subcount[0] = subcount[1] = 0; subheight[0] = subheight[1] = 0; recurse_verify_tree (node->rtavl_link[0], okay, &subcount[0], min, d - 1, &subheight[0]); if (node->rtavl_rtag == RTAVL_CHILD) recurse_verify_tree (node->rtavl_link[1], okay, &subcount[1], d + 1, max, &subheight[1]); *count = 1 + subcount[0] + subcount[1]; *height = 1 + (subheight[0] > subheight[1] ? subheight[0] : subheight[1]); if (subheight[1] - subheight[0] != node->rtavl_balance) { printf (" Balance factor of node %d is %d, but should be %d.\n", d, node->rtavl_balance, subheight[1] - subheight[0]); *okay = 0; } else if (node->rtavl_balance < -1 || node->rtavl_balance > +1) { printf (" Balance factor of node %d is %d.\n", d, node->rtavl_balance); *okay = 0; } }