Which traversal of a binary search tree produces a descending sequence?

Answer 1

Use depth-first traversal. By convention, binary trees place lower values in the left branch and larger or equal values in the right branch. Given any node in the tree (starting from the root), output all the values to the right of that node, then output the node's value, and finally output all the values to the left of that node. The algorithm can be implemented recursively as follows:

void print_descending (node* n) {

if (n->right) print_descending (n->right); // recursively output all values greater than or equal to n->data

printf ("%d\n", n->data); // output the data (assumes an integral type)

if (n->left) print_descending (n->left); // recursively output all values less than n->data

}