be displaced by the new node in the parameter curnode. For appending to the left, this is the head of a non-empty list, while for appending to right, it is the tail. But because of how the linkage is set up to refer back to the sentinel, the code just works for empty lists as well, where curnode will be the sentinel node. Search in a binary tree General declarations, similar to article Binary search tree: struct bst_node { // one node of the binary search tree struct bst_node *child[2]; // each: ->node or end-of-path indicator int key; } ; struct bst { // binary search tree struct bst_node *root; // ->node or end-of-path indicator } *BST; The globally available pointer sentinel to the single deliberately prepared data structure Sentinel = *sentinel is used to indicate the absence of a child. // global variable bst_node Sentinel, *sentinel = &Sentinel; // global initialization Sentinel.child[0] = Sentinel.child[1] = sentinel; BST->root = sentinel; // before the first insertion (not shown) Note that the pointer sentinel has always to represent every leaf of the tree. This has to be maintained by the insert and delete functions. It is, however, about the same effort as when using a NULL pointer. struct bst_node *SearchWithSentinelnode(struct bst *bst, int search_key) { struct bst_node *node; // Prepare the “node” Sentinel for the search: sentinel->key = search_key; for (node = bst->root;;) { if (search_key == node->key) break; if search_key < node->key: node = node->child[0]; // go left else node = node->child[1]; // go right } // Post-processing: if (node != sentinel) return node; // found // search_key is not contained in the tree: return NULL; } Remarks With the use of SearchWithSentinelnode searching loses the R/O property. This means that in applications with concurrency it has to be protected by a mutex, an effort which normally exceeds the savings of the sentinel. SearchWithSentinelnode does not support the tolerance of duplicates. There has to be exactly one “node” to be used as sentinel, but there may be extremely many pointers to it. See also Sentinel value Magic number (programming) Magic string Null object pattern Time formatting and storage bugs Elephant in Cairo Canary value Semipredicate problem References Linked lists Trees (data structures)