Data Structures and Algorithms with C · Lecture Notes

Chapter 12: Threaded Binary Trees

In a linked binary tree, more than half of the pointer fields are empty. A threaded binary tree puts these empty fields to use. An empty left pointer points to the node that comes immediately before the node in inorder; an empty right pointer points to the node that comes immediately after. The tree can then be traversed from start to finish with a single pointer, with no stack and no recursion. These notes first prove how many empty pointers there are, then show how the threads are built, how they are told apart from real links, and what role the header node plays. Next come finding the successor, stack-free inorder and preorder traversal, the Morris traversal, which needs no flag fields, and the procedures insert_right and insert_left, which insert nodes without breaking the threads. For each procedure we give the C code, a line-by-line explanation, a code trace, and a complexity analysis.

Learning outcomes

Counting null pointers
Prove that a binary tree with n nodes has n + 1 null pointers.
Building threads
Apply by hand, to a given tree, the rule that ties an empty left pointer to the inorder predecessor and an empty right pointer to the inorder successor.
Defining the structure completely
Build the C structure of a threaded tree, with the left_thread and right_thread flags and a header node.
Traversing without a stack
Traverse in inorder and preorder with insucc using O(1) extra memory; trace the Morris traversal step by step.
Inserting nodes
Merge the two cases of insert_right into a single procedure and derive insert_left from it.
Writing good code
Decide on a clearly defined procedure, a comment that states the intent, and the right place for the NULL check.

12.1Empty pointers and the idea of a thread

In the linked representation, each node of a binary tree has three fields: a pointer to the left subtree, the data, and a pointer to the right subtree. In C the node is defined as a self-referential struct:

typedef struct node *tree_ptr;
struct node {
    tree_ptr left;   /* left subtree */
    char      data;
    tree_ptr right;   /* right subtree */
};

A pointer in a direction with no child is set to NULL. NULL is the null pointer, which points to no object. Both pointers of a leaf are null. A node with one child has one null pointer. The question for this chapter is simple: how many pointers in a tree are left null, and can these fields be put to any use?

12.1.1n + 1 null pointers in n nodes

Whatever the shape of the tree, the number of null pointers depends only on the number of nodes. A counting argument shows this.

Theorem 12.1 (Number of null pointers)

Every binary tree with n ≥ 1 nodes stored in the linked representation has exactly n + 1 pointer fields equal to NULL.

Each node has two pointer fields, so the tree has 2n fields in total. Every node other than the root receives exactly one pointer, from its parent. A node cannot receive pointers from two different fields, because every node has a single parent. No pointer from inside the tree reaches the root; the root is held by a variable outside the tree. Hence the number of non-null fields is n − 1, and the number of remaining fields is 2n − (n − 1) = n + 1. ∎

The proof never looks at whether the tree is balanced or skewed. Figure 12.1 illustrates this with three examples. The two trees on the left have 4 nodes and very different shapes; both have 5 null pointers. The 10-node tree on the right has 11 null pointers.

ABDCn = 4 NULL = 5ABCDn = 4 NULL = 5ABDHECFJGKn = 10 NULL = 11
Figure 12.1: Three binary trees and their null pointers. The short dashed lines are NULL fields. The two 4-node trees have 5 null pointers and the 10-node tree has 11.

The ratio is striking. Of the 2n fields, n + 1, more than half, carry no information. On a 64-bit machine a pointer takes 8 bytes; in a tree of a million nodes, about 8 MB of memory goes to null pointers. These fields cannot simply be discarded, because it is not known in advance which node will have a child in which direction. But a meaningful value can be stored in them.

Example 12.1

The running example of these notes is a tree with nine nodes. A is the root; B and C are its children. D and E are the children of B; F and G are the children of C; H and I are the children of D. The tree has 2 · 9 = 18 pointer fields. Eight pointers arrive at the eight non-root nodes. The number of null fields is 18 − 8 = 10: two for each of the leaves H, I, E, F, and G. This agrees with n + 1 = 10.

Common mistake

Counting the pointer to the root as a "non-null pointer" and getting n non-null fields. The variable that points to the root (for example tree_ptr root) is not a field of any node in the tree. The non-null fields inside the nodes number only n − 1.

12.1.2The idea of Perlis and Thornton

In 1960 A. J. Perlis and C. Thornton proposed that null pointers could be used to point to other nodes of the tree. They called these pointers threads. A thread is not a real child of the node; it is a signpost that says which node to move to during a traversal.

The value of the idea shows in the extra memory a traversal needs. There are two familiar ways to traverse a binary tree in inorder. A recursive procedure opens one call for each node. The number of calls left open along one path is as large as the height h of the tree, so the call stack uses O(h) memory. The non-recursive (iterative) procedure does the same job with an explicit stack: while going left it pushes the nodes it passes, and later returns to them. That stack also takes O(h) space.

In a balanced tree h is about log2 n, and this cost is small. But in a skewed tree all nodes line up in one direction and h = n. In a left-skewed tree of a million nodes, a recursive traversal keeps a million calls open at the same time. On most systems the default call stack cannot hold that depth, and the program crashes.

In a threaded tree the situation is different. From each node, the next node in inorder, the successor, is reached either directly through a thread or by following a few real links. Because the way back is written inside the tree, nothing has to be remembered. The traversal is done with a single pointer variable, and the extra memory is O(1). There is a price: for each pointer field we must keep one bit of information saying whether it is a real child or a thread.

Table 12.1: Three ways to traverse in inorder. h is the height of the tree; in a skewed tree h = n.
MethodTimeExtra memoryWhat is remembered
RecursiveO(n)O(h)Open calls (the call stack)
Non-recursive, with a stackO(n)O(h)The nodes passed while going left
ThreadedO(n)O(1)Nothing; the way back is written in the tree

12.2Building the threads

Which node an empty pointer should point to is not arbitrary. The rule is set by the inorder traversal sequence. So the notions of "previous" and "next" node in that sequence must first be made precise.

12.2.1Inorder predecessor and successor

At each node, an inorder traversal visits the left subtree first, then the node itself, and the right subtree last. In the running example the sequence is H D I B E A F C G. In this sequence every node has a known neighbor on its left and one on its right.

Definition 12.1

The inorder predecessor of a node p is the node visited immediately before p in an inorder traversal. The inorder successor of p is the node visited immediately after p. The first node in the sequence has no predecessor, and the last node has no successor.

In the example sequence, the predecessor of E is B and its successor is A. H has no predecessor because it is the first node; G has no successor because it is the last. The rule for threads is written with these two notions.

Definition 12.2

A threaded binary tree is a binary tree whose null pointers have been filled according to the following two rules:

  1. If p->left_child == NULL, then p->left_child points to the inorder predecessor of p.
  2. If p->right_child == NULL, then p->right_child points to the inorder successor of p.

The pointers filled in this way are called threads.

Figure 12.2 shows the rules applied to the running example. The solid blue lines are real child links. The dashed red arrows are threads. The threads weave the inorder sequence of the tree into the tree itself: the red arrow leaving each leaf to the right goes to the next node in the sequence.

headABDHIECFGinorder: H D I B E A F C G
Figure 12.2: The running example with threads. The dashed red arrows are threads: a left thread goes to the predecessor and a right thread goes to the successor. The left thread of H and the right thread of G have no node to point to.

The threads have one property in common: all of them point upward to a node in the tree. The reason is this. The predecessor of a node with no left subtree is the nearest ancestor whose right subtree contains the node. Likewise, the successor of a node with no right subtree is the nearest ancestor whose left subtree contains the node. For example, I lies in the left subtree of B and has no right subtree; the successor of I is B. Going down is done with real links, and returning upward with threads. The information a stack has to remember is exactly these return paths.

12.2.2Building the threads one by one

To build the threads by hand, first write down the inorder sequence. Then, for each empty pointer, read off the node immediately to the left or to the right of the node in that sequence. The running example has ten empty fields (Example 12.1). Table 12.2 gives the target of each one.

Table 12.2: Building the ten threads from the inorder sequence H D I B E A F C G. For the "head" rows there is no node to point to; these two threads will be tied to the header node.
StepEmpty fieldRuleNode pointed to
1left of Hpredecessornone (head)
2right of HsuccessorD
3left of IpredecessorD
4right of IsuccessorB
5left of EpredecessorB
6right of EsuccessorA
7left of FpredecessorA
8right of FsuccessorC
9left of GpredecessorC
10right of Gsuccessornone (head)

Each row of the table corresponds to an adjacency in the sequence. The inorder sequence has eight pairs of neighbors (H–D, D–I, …, C–G). Each pair of neighbors is tied by exactly one thread, even for pairs such as D and H that are also joined by a real link (the right thread of H points to D). The remaining two threads sit at the two ends of the sequence. Figure 12.3 shows the beginning and the end of the construction. At the top is the ordinary tree with its ten null pointers; at the bottom all ten threads are in place. The inorder sequence is also written under the lower figure, so one can check that each red arrow points to a neighbor in this sequence.

ABDHIECFGHDIBEAFCG
ABDHIECFGHDIBEAFCG
Figure 12.3: The first and last states of building threads. Top: the ordinary tree with 9 nodes and its 10 null pointers (short dashed lines). Bottom: all null pointers tied to a predecessor or successor; the left thread of H and the right thread of G are still dangling.
Example 12.2

Build the threads of the tree A(B(D, E), C(–, F)): A has children B and C, B has children D and E, and C has only a right child F. The inorder sequence is D B E A C F. The number of nodes is 6, and the number of empty fields is 6 + 1 = 7.

  • Left of D: no predecessor, so the head. Right of D: successor B.
  • Left of E: predecessor B. Right of E: successor A.
  • Left of C: predecessor A. C has a right subtree (F), so its right pointer is a real link.
  • Left of F: predecessor C. Right of F: no successor, so the head.

There are 7 threads in all, 2 of which go to the header node. The left thread of C deserves attention: because the left of C is empty, the predecessor of C is A. A is the parent of C; this time the thread points to the parent.

12.2.3Thread flags

On paper, threads are drawn in red and real links in black. To the compiler there is no difference between the two pointers: both are the address of a node. When a traversal procedure follows p->left_child, it cannot tell from the address alone whether it will descend to a real left child or return to a predecessor above. So next to each pointer we store information about its kind. Two extra fields are added to each node:

typedef struct threaded_tree *thread_ptr;
struct threaded_tree {
    short int    left_thread; /* TRUE: left_child is a thread */
    thread_ptr left_child;
    char         data;
    thread_ptr right_child;
    short int    right_thread; /* TRUE: right_child is a thread */
};

The structure adds two fields to the ordinary binary tree node. If left_thread is true (TRUE), then left_child is a thread, that is, it points to the predecessor; if it is false (FALSE), it points to a real left child. right_thread carries the same information for the right pointer. The constants TRUE and FALSE are defined with an enumeration type:

enum { FALSE, TRUE };      /* FALSE = 0, TRUE = 1 */

In an enumeration type the first name gets 0 and the second gets 1. So FALSE is 0 and TRUE is 1, and conditions such as if (p->left_thread) work directly. The typedef in the first line gives the type struct threaded_tree * the short name thread_ptr. This line comes before the definition of the structure; since the fields of the structure hold pointers to its own type, the name must be known first. The structure definition ends with a semicolon after the closing brace (line 8). If this semicolon is forgotten, the compiler usually reports the error on the next line, and the location of the mistake becomes confusing.

Don't the flags increase memory? They do, but the gain in time is much greater. The lecture states this decision openly: time complexity matters more than space complexity, and the two flags can in fact be stored in two bits. It is instructive to measure how much space is spent. The size of a structure is not just the sum of its fields. The compiler places each field on its own alignment boundary and inserts padding bytes between them. Table 12.3 gives the values measured on x86-64 with sizeof and offsetof.

Table 12.3: Memory layout of struct threaded_tree (x86-64, pointer 8 bytes, short 2 bytes). The measured sizeof is 40 bytes.
FieldOffset (bytes)SizePadding after it
left_thread026
left_child880
data1617
right_child2480
right_thread3226

Of the 40 bytes, 19 are padding. Pointers must be placed at addresses that are multiples of 8; the small fields in between each occupy a whole 8-byte slot by themselves. If the fields are ordered from large to small (first the two pointers, then the two shorts, and char last), the same structure shrinks to 24 bytes. An ordinary node without flags is also 24 bytes. So if the field order is chosen well, the flags add no memory at all on this machine; they fit into the padding bytes that would otherwise be left empty behind the two pointers. Defining the flags as bit fields (unsigned left_thread : 1) does not change the result. The field order in the slides follows the node's drawing on paper: left flag, left pointer, data, right pointer, right flag. This order makes reading easier, but it is the most wasteful layout in memory.

Common mistake

Treating left_child or right_child as a real child without looking at the flag. In a threaded tree no pointer is NULL. A loop such as while (p->left_child != NULL) p = p->left_child;, written for an ordinary tree, never stops in a threaded tree. The left thread of the leftmost node goes to the head, and the left of the head goes back to the root; the loop runs forever. In a threaded tree every descent is checked with the flag.

12.2.4The header node

In Table 12.2 two threads were left dangling. The left pointer of H should point to a predecessor, but H is the first node in the sequence. The right pointer of G should point to a successor, but G is the last node. Writing NULL into these two fields would break the "no pointer is null" arrangement and add special cases to the traversal procedures. The solution is the header node, familiar from linked lists.

Definition 12.3

The header node of a threaded tree is an extra node that carries no data and stands outside the tree. The root of the real tree is reached through L->left_child. The right pointer of the header always points to itself, and its right_thread field is FALSE. The two threads that have no node to point to, that is, the left thread of the first node and the right thread of the last node, point to the header.

In an empty tree there is only the header. In that case the left pointer of the header also points to itself, and left_thread is TRUE: what it points to is not a real root but a thread. When the first node is inserted, the left pointer is redirected to that node and left_thread is set to FALSE.

Table 12.4: The fields of the header, the only node of an empty threaded tree.
left_threadleft_childdataright_childright_thread
TRUE→ head–→ headFALSE

This arrangement is built by a C procedure. Two small helpers that do not appear in the slides are written. new_node allocates memory for a new node. empty_threaded_tree fills in the header as in Table 12.4:

thread_ptr new_node(char data) {
  thread_ptr d = malloc(sizeof *d);
  if (d == NULL) {               // out of memory
    fprintf(stderr, "out of memory\n");
    exit(EXIT_FAILURE);
  }
  d->data = data;
  d->left_child = d->right_child = NULL;   // insertion fills these in
  d->left_thread = d->right_thread = TRUE;
  return d;
}
thread_ptr empty_threaded_tree(void) {
  thread_ptr L = new_node('-');  // head: data unused
  L->left_child = L;  L->left_thread = TRUE;   // tree is empty
  L->right_child = L;  L->right_thread = FALSE;  // right is always itself
  return L;
}

malloc returns NULL if it cannot find the requested memory. Writing to d->data without checking the returned value means writing through a null pointer, which is undefined behavior. For this reason the procedure prints a message and ends the program when it gets NULL. The expression sizeof *d gives the size of the type that d points to. Because the type name is not repeated, the expression stays correct even if the structure changes. The pointers of the new node are set to NULL; when the node is inserted into a tree, insert_right or insert_left overwrites these values. For the same reason the initial values of the flags do not matter. In empty_threaded_tree, '-' is written into the data of the header; this value is never read.

The upper half of Figure 12.4 shows the empty tree and the lower half shows the running example with its header. The letters T and F in the figure are the thread flags on the two sides of each node. The left of the header goes to the root (A), and its left flag is F. The left thread of H and the right thread of G are now tied to the header. The right pointer of the header curls back onto itself.

headTFleft_child → itself (thread, TRUE)right_child → itself (FALSE)
headFFAFFBFFDFFHTTITTETTCFFFTTGTT
Figure 12.4: The header node. Top: the empty tree, where both pointers of the header point to itself. Bottom: the full tree, where the left of the header goes to the root and the two dangling threads are tied to the header. T and F are the thread flag of the node on that side.

With the header, the tree closes into a ring. In inorder, after the last node comes the header, and after the header the first node again. The traversal procedures use this ring: they start from the header and stop when they return to it. So special cases such as "is the tree empty", "which node is first", and "the last node has no successor" need no separate if.

12.2.5Why inorder

The threads are built according to the inorder sequence. The three traversal orders of the same tree are side by side in Table 12.5.

Table 12.5: The three traversal orders of the running example.
TraversalRuleOrder
inorderleft, root, rightH D I B E A F C G
preorderroot, left, rightA B D H I E C F G
postorderleft, right, rootH I D E B F G C A

The privilege of inorder comes from the consistency of the threads. In this order, the predecessor of a node with no left subtree is always an ancestor; so is the successor of a node with no right subtree. So an empty left field is exactly suited to point to the predecessor, and an empty right field exactly suited to point to the successor. Non-empty fields go downward, and the predecessor or successor is found at the far right or far left of that subtree. Together, the two rules make it possible to find the successor and the predecessor of every node by a short path. In preorder this symmetry is missing. For example, the preorder successor of D is H, and a real left link already goes from D to H; no information is left for a thread to add. For this reason the lecture stresses that the tree is built for inorder traversal. Preorder and postorder traversal can also be done with the same threads, but in a more roundabout way.

12.3Inorder traversal

All traversal procedures of a threaded tree rest on a single question: which node is the inorder successor of a given node? If this question can be answered quickly, a traversal consists simply of starting at the header and moving from successor to successor.

12.3.1Finding the successor

For the successor of a node p there are two cases.

  • If p->right_thread == TRUE, then p->right_child is a thread. By the definition of a thread, this pointer already points to the successor of p. No search is needed.
  • If p->right_thread == FALSE, then p has a real right subtree. After writing p, an inorder traversal enters this subtree and writes its leftmost node first. The successor is the leftmost node of the right subtree. To reach it, start from the right child and follow left links until left_thread is TRUE.

These two rules fit in a few lines in the procedure from the slides:

thread_ptr insucc(thread_ptr L) {
  // successor of the (non-NULL) node L
  thread_ptr p = L->right_child;
  if (!L->right_thread)        // is there a right subtree
    while (!p->left_thread)   // descend to its leftmost node
      p = p->left_child;
  return p;
}

The procedure works line by line as follows.

  • Lines 1–2. The procedure takes a node pointer and returns the address of the successor. The comment states the precondition: L must not be NULL. In a threaded tree no pointer is NULL, so no such check is needed inside the procedure; satisfying the precondition is the caller's job.
  • Line 3. p receives the right pointer of L. This value is both the result directly in the thread case and the starting point of the search in the right-subtree case. The first step common to the two cases is merged into a single assignment.
  • Line 4. If !L->right_thread is true, the right pointer is a real link, that is, there is a right subtree. The comment writes the meaning of the question, not the flag: "is there a right subtree".
  • Lines 5–6. In the right subtree we descend to the left. The loop condition looks at p->left_thread, not at p->left_child. The left pointer of the leftmost node is also a filled field (a thread), but its flag is TRUE.
  • Line 7. In both cases p points to the successor, and it is returned.

The correctness of the rules follows from the definition of inorder traversal.

Theorem 12.2 (Successor rule)

In a threaded binary tree, if p has a right subtree, its successor is the leftmost node of that subtree. If it has no right subtree, its successor is the node that the thread p->right_child points to. insucc returns this node in both cases.

Immediately after writing p, an inorder traversal begins to traverse the right subtree of p. The traversal of a subtree always opens with its leftmost node: from the root we go down to the left, and the first node with no left child is written. So if there is a right subtree, the first node written after p is the leftmost node of that subtree. The loop of the procedure follows left links until the first node with no left child, that is, one whose left_thread is TRUE; this node is the leftmost node. If there is no right subtree, p->right_child is a thread and, by the second rule of Definition 12.2, points to the successor. ∎

12.3.2Code trace: head, A, and I

Let the procedure be called with three different nodes. Table 12.6 gives, for each call, the values p takes and the flags that decide, in order. The line numbers refer to the code above.

Table 12.6: Trace of insucc. The tree is the running example with its header (Figure 12.4, bottom).
CallLineEventp
L = head3p = head->right_child; the right of the head is itselfhead
4right_thread is FALSE: the head is taken to have a real right subtreehead
5–6head->left_thread is FALSE, go leftA
5–6A->left_thread is FALSE, go leftB
5–6B->left_thread is FALSE, go leftD
5–6D->left_thread is FALSE, go leftH
7H->left_thread is TRUE: the loop ends, H is returnedH
L = A3p = A->right_childC
4right_thread is FALSE: A has a right subtreeC
5–6C->left_thread is FALSE, go leftF
7F->left_thread is TRUE: F is returnedF
L = I3p = I->right_child (a thread)B
4right_thread is TRUE: the loop is not enteredB
7B is returnedB

The first call gives a special result: the successor of the head is the first node in inorder (H). The right pointer of the head pointing to itself and its right_thread being FALSE are chosen for exactly this. The procedure thinks of the "right subtree" of the head as the head itself, starts descending to the left from there, and reaches the leftmost node of the real tree on the left of the head. So no separate "find the leftmost node" procedure is needed to start a traversal. Figure 12.5 shows the first and last moments of this call.

headFFAFFBFFDFFHTTITTETTCFFFTTGTTL,p
headFFAFFBFFDFFHTTITTETTCFFFTTGTTLp
Figure 12.5: insucc(head). Top, the start: L and p point to the head. Bottom: p has descended to H by following left links; since the left flag of H is T, the search stops.

In the call for A, the right subtree starts at C, and a single step to the left finds F. In the call for I there is no search at all; the right pointer is a thread and points directly to B. The successor of a leaf is always found in a single step like this.

Common mistake

Writing the loop as while (!L->left_thread) instead of while (!p->left_thread). Since the condition looks at the same node on every iteration, the loop is either never entered or never left. The loop variable is p, and the condition must test its flag.

12.3.3Traversal without a stack

Once the successor procedure is ready, inorder traversal is a short loop. We start at the header; on each iteration we move to the next node and write it. When we return to the header, the whole tree has been traversed.

void tinorder(thread_ptr L) {
  thread_ptr p = L;        // L: the header node
  for (;;) {
    p = insucc(p);
    if (p == L) break;       // back at the head?
    printf("%c ", p->data);
  }
}
  • Line 2. p points to the header. The entire state of the traversal is in this single variable.
  • Line 3. for (;;) is an unconditional loop; the exit is made by the break in the body. The condition cannot be put at the top of the loop, because the exit test has to be made after the successor is found.
  • Line 4. p advances to its own successor.
  • Line 5. If the successor is the header, the ring is complete. Since the right thread of the last node points to the header, this always happens.
  • Line 6. The node is written.

In an empty tree the first call returns the header itself. p = head->right_child is the header. Because right_thread is FALSE, the loop is entered, but the left_thread of the header is TRUE, so it exits immediately. p == L is true, and the traversal ends without writing anything. Needing no separate check for the empty tree is the gain from the header node.

In the running example the loop runs ten times. Table 12.7 gives, for each iteration, the rule by which the successor was found and how many pointers were followed. The "Followed" column counts the read in line 3 and each descent to the left in the loop as one step each.

Table 12.7: Trace of tinorder. The output is H D I B E A F C G; 15 pointers are followed in total.
Iterationp (before)How it was foundp (after)FollowedOutput
1headleftmost of the right subtree (A, B, D, H)H5H
2Hdirectly through a threadD1D
3Dleftmost of the right subtree (I)I1I
4Idirectly through a threadB1B
5Bleftmost of the right subtree (E)E1E
6Edirectly through a threadA1A
7Aleftmost of the right subtree (C, F)F2F
8Fdirectly through a threadC1C
9Cleftmost of the right subtree (G)G1G
10Gdirectly through a threadhead1(break)

The two rules in the table follow one another in turn. After a leaf we go up through a thread; after an internal node we enter the right subtree and descend to the far left. No node is written twice in any iteration, and a stack is needed nowhere.

12.3.4The cost of the traversal

A single call of insucc can take a long time. The first call, made with the header, descends from the root to the leftmost node; this path is as long as the height of the tree. The worst cost of a single call is therefore O(h). In a left-skewed tree of 1000 nodes this first call follows 1001 pointers. But the total cost of the whole traversal is far smaller than the product of the number of calls and the worst cost.

Theorem 12.3 (Cost of a threaded traversal)

Traversing a threaded tree of n nodes with tinorder follows at most 2n + 1 pointers. The time is Θ(n) and the extra memory is O(1).

The loop calls insucc n + 1 times: once for each of the n nodes and once for the return to the header. Each call reads exactly one pointer in line 3, which adds up to n + 1 steps. The descents to the left in the loop go only over real left links. A left link is followed only when entering, from the left, the subtree that contains the node owning the link, and the traversal enters each subtree once. So each real left link is followed at most once. The number of real left links, counting the link from the header to the root, is at most n. The total is (n + 1) + n = 2n + 1. Each step takes constant time, so the time is O(n). Since every node is written, the time is also Ω(n). The procedure uses only the variable p; the extra memory is O(1). ∎

In the running example, the nodes with a left child are A, B, C, and D. Together with the link from the header to the root, five descents to the left are made. The total 10 + 5 = 15 steps equals the sum of the last column of Table 12.7. The extreme cases were also checked by counting. In a left-skewed tree of 1000 nodes every node has a left child and the bound is reached exactly: 2001 steps. In a right-skewed tree of 1000 nodes only one descent to the left is made, from the header to the root: 1001 + 1 = 1002 steps.

Dividing the total of 2n + 1 steps among n + 1 calls leaves fewer than two steps per call. Although there are expensive calls when looked at one by one, they are few in a traversal; an expensive descent makes the following calls cheap. This kind of accounting is called amortized analysis. The amortized cost of finding a successor within a traversal is O(1).

Threads bring one more gain. Once the address of any node is at hand, its successor can be reached without starting the traversal from the beginning. In an ordinary tree, finding the successor of a node requires either a parent pointer or a fresh descent from the root. A threaded tree answers this question starting from the node itself.

The value of such an improvement should not be underestimated. The lecture gives an example: a problem is known to be solved in O(n2) time, and someone works out an algorithm that brings it down to O(n1.89). This small difference in the exponent is a big achievement, and that algorithm goes into the literature. Threaded traversal improves not time but memory: it brings O(h) down to O(1). In skewed trees that means going from O(n) to O(1).

12.3.5Preorder traversal

The threads are built for inorder, but the same threads can also be used for preorder traversal. For this we write a procedure that finds the preorder successor.

thread_ptr presucc(thread_ptr p) {
  if (!p->left_thread)        // the left child, if any
    return p->left_child;
  while (p->right_thread)      // climb the right threads
    p = p->right_child;
  return p->right_child;        // first real right child
}

In a preorder traversal, after a node is written, its left subtree is entered if there is one; the first node of the left subtree is its root. Lines 2–3 handle this case: if the left flag is FALSE, the successor is the left child. If there is no left child, the successor is the root of the first not-yet-traversed right subtree found above, starting from p. Lines 4–5 look for this node. As long as the right pointer of p is a thread, the thread is followed. The right thread goes to the inorder successor, that is, to the nearest ancestor that carries p in its left subtree. The left subtree of that ancestor is finished, and next comes the right subtree of the ancestor. If that ancestor also has no right subtree (its flag is again TRUE), one more thread is followed. We stop at the first node with a real right link, and line 6 returns its right child.

The traversal loop using this procedure has the same form as the inorder traversal:

void tpreorder(thread_ptr L) {
  thread_ptr p = L;        // L: the header node
  for (;;) {
    p = presucc(p);
    if (p == L) break;       // back at the head?
    printf("%c ", p->data);
  }
}

Starting from the header, the left flag of the header is FALSE, so the successor is the root (A). After the last node, the threads climb up to the header; the right flag of the header is FALSE and its right pointer is itself. The procedure returns the header and the traversal ends. Table 12.8 gives all the steps.

Table 12.8: Traversal with presucc. The output is A B D H I E C F G.
pLeft flagRight threads followedSuccessor
headF–A (left child)
AF–B (left child)
BF–D (left child)
DF–H (left child)
HTH → DI (right child of D)
ITI → BE (right child of B)
ETE → AC (right child of A)
CF–F (left child)
FTF → CG (right child of C)
GTG → headhead (the right of the head is itself): done

Finding the preorder successor of a leaf may require following several threads. For example, after I we climb to B through one thread and find the right child of B, E. In a deeper tree, starting from a leaf, several ancestors in a row may have no right subtree; in that case the chain of threads gets longer. Even so, each right thread is followed at most once in the whole traversal, so the total time stays O(n) and the extra memory O(1).

Postorder traversal cannot be written as easily. In postorder, a node is usually followed by its parent. If the node is the right child of its parent, its successor is the parent; if it is the left child, its successor is the first postorder node in the parent's right subtree. In both cases the parent must be known. Threads point not to the parent but to the inorder predecessor and successor, and these two do not always coincide with the parent. The right thread of H points to its parent D, but the right thread of I points not to its parent D but to B. Postorder traversal with threads is possible but roundabout. Adding a parent pointer to each node makes the job easier.

12.3.6The Morris traversal

A threaded tree pays two costs: flag fields in every node, and the extra complexity of the insertion procedures. In 1979 J. M. Morris proposed a method that needs no flag fields. The Morris traversal builds the threads temporarily during the traversal in an ordinary binary tree and removes them when it is done. At the end of the traversal the tree returns to its original state. The procedure works with the ordinary struct node node given at the beginning of the chapter:

void morris_inorder(tree_ptr L) {
  while (L) {
    if (!L->left) {             /* no left: print, go right */
      printf("%c", L->data);  L = L->right;
    } else {
      tree_ptr p = L->left;    /* inorder predecessor */
      while (p->right && p->right != L)
        p = p->right;
      if (!p->right) {           /* set a temporary thread */
        p->right = L;  L = L->left;
      } else {                      /* remove the thread */
        p->right = NULL;
        printf("%c", L->data);  L = L->right;
      }
    }
  }
}

The idea of the procedure is this. When we arrive at a node L that has a left subtree, we prepare the way back before going left. The inorder predecessor of L is the rightmost node of its left subtree. The right pointer of this node is null, because the rightmost node cannot have a right child. We write the address of L into this empty field: a temporary thread. After the left subtree has been traversed and the predecessor is reached, following this thread leads back to L. When we reach L a second time, the predecessor is searched for again; this time the right pointer of the predecessor is seen to point to L. This is the sign that the left subtree is finished. The thread is removed, L is written, and we move right.

  • Line 2. The loop runs until L becomes NULL. The right pointer of the last node really is NULL; the loop ends there.
  • Lines 3–4. If there is no left subtree, the node is written and we move right. The right pointer may be a real child or a temporary thread set earlier. The procedure does not distinguish the two; in both cases it goes to the right node.
  • Lines 6–8. The predecessor is searched for: start from the left child and go right as long as possible. The second half of the condition (p->right != L) is important. If the thread has been set earlier, the right pointer of the rightmost node points to L; without this test the search would follow the thread to L and from there turn left again.
  • Lines 9–10. If the right of the predecessor is null, this is the first visit: the thread is set and we descend to the left.
  • Lines 11–13. If the right of the predecessor points to L, this is the second visit: the thread is removed, L is written, and we move right.

Let us trace the procedure on the tree A(B(D, E), C): the five-node tree in which A has children B and C, and B has children D and E. Table 12.9 shows each iteration and Figure 12.6 shows four moments.

Table 12.9: Trace of morris_inorder, tree A(B(D, E), C). The output is DBEAC.
IterationLPredecessor pEventTemporary threadsOutput
1AE (right from B)the right of E is empty: set the thread, go leftE→A
2BDthe right of D is empty: set the thread, go leftE→A, D→B
3D–no left child: write, go right (through the thread to B)E→A, D→BD
4BDthe right of D is B: remove the thread, write, go rightE→ADB
5E–no left child: write, go right (through the thread to A)E→ADBE
6AE (right from B)the right of E is A: remove the thread, write, go right–DBEA
7C–no left child: write, go right (NULL)–DBEAC
ABDECLoutput: ABDECLoutput: ABDECLoutput: DBABDECoutput: DBEAC
Figure 12.6: Four moments of the Morris traversal. In the first, the thread E → A has been set and we have gone left. In the second, the thread D → B has been set as well. In the third, we have returned from D to B, the thread D → B has been removed, and B has been written. In the fourth, the traversal is finished; the tree is in its original state.

The table shows that every temporary thread is seen exactly twice: when it is set and when it is removed. Every node with a left child gives rise to one thread; in this tree there are two (for A and B). When the traversal ends, the right pointers of D and E are NULL again. The result was checked by comparing it with the output of a recursive inorder traversal of the same tree:

void inorder(tree_ptr p) {
  if (p) {
    inorder(p->left);
    printf("%c", p->data);
    inorder(p->right);
  }
}

The time of the Morris traversal is also O(n). For each node with a left child the predecessor is searched for twice. Each search walks a path that starts at the left child and goes right. These paths for different nodes share no edge; an edge lies on the predecessor path of at most one node. The total length of the paths is therefore at most n − 1, and walking them twice bounds the total by 2(n − 1). To this is added the constant work done at each node. Measurement confirms this: the five-node example makes 13 pointer moves in all, and the complete seven-node tree makes 18.

The method has a limit. While the traversal is in progress, the tree is temporarily modified: some NULL fields point to other nodes. If another thread reads the tree during this time, it meets cycles and gets a wrong result. If the traversal is cut short by an error or an early exit, the tree is left corrupted. The Morris traversal is therefore suitable for procedures that have the tree to themselves and carry the traversal through to the end.

12.4Inserting a node

Traversal in a threaded tree is easy; the price is paid at insertion. Inserting a node into a binary search tree is a single pointer assignment: the new node is written into an empty child field. In a threaded tree there are no empty fields. When a new node is inserted, both its own threads must point to the right places and the threads around it must be adjusted to the new order. Insertion is therefore not an easy procedure on its own; it is a little intricate.

12.4.1Why insertion is intricate

A new node is inserted either to the right or to the left of a parent. The pointer assignments for left and right insertion are mirror images of each other, but they are not literally identical; so two separate procedures are written: insert_right and insert_left. Let us deal with insert_right first. There are two cases in inserting on the right:

  1. The parent has no right subtree. The new node is placed to the right of the parent as a leaf.
  2. The parent has a right subtree. The new node goes in between the parent and this subtree; the old subtree becomes the right subtree of the new node.

The second case never arises in inserting into an ordinary binary search tree; there the new node is always a leaf. In a threaded tree both cases are useful: the second is a way to put a node into the middle of the tree.

12.4.2Case 1: inserting under a parent with no right subtree

Let the tree be A(–, B(C, –)): A is on the left of the head; A has no left child and has right child B; B has left child C and no right child. The inorder sequence is A C B. The new node D will be inserted to the right of B. The right pointer of B is a thread, and since B is the last node in the sequence, it points to the head. The insertion is done with six assignments:

child->right_child  = parent->right_child;
child->right_thread = TRUE;  // parent had no right child
child->left_child  = parent;
child->left_thread = TRUE;
parent->right_child   = child;
parent->right_thread = FALSE;  // was TRUE

The reason for each assignment can be read off the inorder sequence. After the insertion the sequence will be A C B D. D comes immediately after B; the predecessor of D is B, and its successor is the old successor of B. Table 12.10 follows the assignments in order, and Figure 12.7 shows the first and last states.

Table 12.10: Trace of Case 1: parent = B, child = D.
LineAssignmentResultReason
1child->right_child = parent->right_childD → headThe successor of the parent is now the successor of the child. It does not matter whether this successor is the head.
2child->right_thread = TRUEred arrowThe parent had no right subtree; the child, being a leaf, has none either.
3child->left_child = parentD → BThe predecessor of the child is the parent.
4child->left_thread = TRUEred arrowThis is a thread as well.
5parent->right_child = childB → DA real link from the parent to the child.
6parent->right_thread = FALSEblack linkThe right of the parent is no longer a thread but a real child.
headFFATFBFTCTTparentchildDchildFF
headFFATFBFFCTTDTTparentchild
Figure 12.7: Case 1. Top, after the first assignment: D is not yet attached to the tree; its right pointer points to the head, which is the successor of B. Bottom, after the six assignments: D is the real right child of B; the left thread of D points to B and its right thread points to the head.

The order of the assignments is not arbitrary. Line 1 reads the right pointer of the parent, and line 5 overwrites it. If the places of these two lines are exchanged, child->right_child receives the child's own address instead of the old successor of the parent, and the successor information is lost. The general rule is this: if the old value of a field is needed, use that value first and only then change the field. All the assignments take constant time; the cost of Case 1 is O(1).

12.4.3Case 2: the parent has a right subtree

Now let the tree be A(–, B(C, D(E, F))). The right child of B is D, and the children of D are E and F. The inorder sequence is A C B E D F. The new node X will be made the right child of B. What we want is that the subtree of D must not be lost and must become the right subtree of X. The red pointers must again point to the right places. After the insertion the sequence will be A C B X E D F.

Two requirements are read from this sequence. The predecessor of X is B; this is as in Case 1. But the node that comes after X is E, the leftmost node of the subtree of D. The left thread of E used to point to B, because the old predecessor of E was B. After the insertion the predecessor of E becomes X. So the child must be made the predecessor of the old successor of the parent.

What happens if the six assignments of Case 1 are applied as they are to this tree? The result of trying it is this: the traversal writes A C B X D F; E is lost. The cause is line 2. child->right_thread = TRUE treats the right pointer of X (which points to D) as a thread. After X, the traversal jumps directly to D by the thread rule and never descends into the left subtree of D. The left thread of E also still points to B. The tree is corrupted, and no compiler warning announces it.

The fix has two parts:

  • Line 2 is written as child->right_thread = parent->right_thread. In Case 1 the flag of the parent is TRUE, and the thread status passes to the child; in Case 2 it is FALSE, and the real-link status is preserved. The subtree of the parent has now become the subtree of the child.
  • In Case 2, the left thread of the old successor of the parent, that is, of the successor of the child in the new arrangement, is redirected to the child.

With these two changes a single procedure that handles both cases can be written.

12.4.4One procedure: insert_right

void insert_right(thread_ptr parent,
               thread_ptr child) {
  // make child the right child of parent (threaded)
  thread_ptr p;
  child->right_child   = parent->right_child;
  child->right_thread = parent->right_thread;
  child->left_child   = parent;
  child->left_thread = TRUE;
  parent->right_child    = child;
  parent->right_thread  = FALSE;
  if (!child->right_thread) { // did parent have a subtree?
    p = insucc(child);
    p->left_child = child;     // successor's predecessor is child
  }
}

The procedure reads line by line as follows. The line numbers refer to the code above.

  • Lines 1–2, a clear definition. The name of the procedure says what it does; the incoming parameters (parent, child) are clear; there is no return value (void). A clearly defined procedure can be used without reading its body.
  • Lines 5–6. The right pointer and right flag of the child are taken from the parent. In Case 1 the thread status (TRUE) is kept, and in Case 2 the real-link status (FALSE). The common work is written in a common form.
  • Lines 7–8. The predecessor of the child is the parent: the left pointer goes to the parent and the left flag becomes TRUE.
  • Line 9. A real link from the parent to the child.
  • Line 10. The right flag of the parent is set to FALSE. In Case 2 the flag is already FALSE, so this assignment is unnecessary but harmless; in Case 1 it is needed. Writing it in both cases, instead of separating them with an if, simplifies the code.
  • Lines 11–13. If the right flag of the child is FALSE, the child has a real right subtree; this is Case 2. The successor of the child is found and its left thread is redirected to the child. In Case 1 only one test is made and the procedure exits.

The condition in line 11 tests a flag, but the question it asks is this: did the parent have a right subtree? After lines 5–6, the old right information of the parent has been moved to the child, so this question is answered by looking at the flag of the child. The comment writes this question, not the flag.

Table 12.11 traces the call insert_right(B, X) line by line on the Case 2 tree.

Table 12.11: Trace of insert_right(B, X), tree A(–, B(C, D(E, F))). The resulting sequence is A C B X E D F.
LineEventChanged field
5The old right subtree of B goes to the right of XX->right_child = D
6The flag of B was FALSE; the real-link status is keptX->right_thread = FALSE
7The predecessor of X is BX->left_child = B
8red arrowX->left_thread = TRUE
9A real link from B to XB->right_child = X
10it was already FALSE; harmlessB->right_thread = FALSE
11!X->right_thread is true: X has a right subtree–
12The successor of X: descend left from D and stop at Ep = E
13The left thread of E points to X instead of BE->left_child = X
headFFATFBFFCTTDFFETTFTTparentchildXchildFF
headFFATFBFFCTTXTFDFFETTFTTparentchild
Figure 12.8: insert_right(B, X), Case 2. Top, after the first assignment: the right of X points to D, X is not yet attached to the tree, and the left thread of E points to B. Bottom, after the procedure finishes: X is between B and D; the left thread of E points to X.

After line 10 the tree is almost correct; X is in place, and even the traversal writes A C B X E D F, because the traversal does not use left threads. But the left thread of E still points to B. A procedure that traverses backwards in inorder or looks for a predecessor exposes this bug at once. The lecture warns at this point: one should not decide right away that the code works correctly; there is still an if block to be executed.

The same procedure was also tried on the Case 1 tree. insert_right(B, D) on the tree A(–, B(C, –)) gives the same result as the six-assignment code: the sequence A C B D, the left thread of D pointing to B, and its right thread pointing to the head. Because the flag of the parent is TRUE, the condition in line 11 is false and the if block does not run.

Cost. Lines 5–10 take constant time. The successor search in line 12 descends to the left in the right subtree of the child; this path is at most as long as the height of the tree. The time of insert_right is O(h) in the worst case and O(1) in Case 1. The extra memory is O(1).

12.4.5Inserting on the left

insert_left makes the node pointed to by child the left child of the parent. The procedure is the mirror image of insert_right: left and right, and predecessor and successor, are exchanged. The old predecessor of the parent becomes the predecessor of the child. If the parent has a left subtree, the right thread of the rightmost node of that subtree, that is, of the new predecessor of the child, is redirected to the child. For this we need a procedure that finds the inorder predecessor. The predecessor rule is the mirror image of the successor rule: the rightmost node of the left subtree if there is one, otherwise the node that the left thread points to.

thread_ptr inpred(thread_ptr L) {
  thread_ptr p = L->left_child;
  if (!L->left_thread)
    while (!p->right_thread) p = p->right_child;
  return p;
}
void insert_left(thread_ptr parent, thread_ptr child) {
  child->left_child   = parent->left_child;
  child->left_thread = parent->left_thread;
  child->right_child   = parent;
  child->right_thread = TRUE;      // successor is parent
  parent->left_child    = child;
  parent->left_thread  = FALSE;
  if (!child->left_thread) {      // parent had a left subtree
    thread_ptr p = inpred(child);
    p->right_child = child;         // predecessor's successor is child
  }
}
Table 12.12: The mirror relation between insert_right and insert_left.
insert_rightinsert_left
child->right_child = parent->right_childchild->left_child = parent->left_child
child->right_thread = parent->right_threadchild->left_thread = parent->left_thread
child->left_child = parent (the parent is its predecessor)child->right_child = parent (the parent is its successor)
parent->right_thread = FALSEparent->left_thread = FALSE
left thread of the successor to the childright thread of the predecessor to the child
insucc: right, then left and leftinpred: left, then right and right
Example 12.3

Let the tree be A(B(D, E), C); the inorder sequence is D B E A C. Let insert_left(A, X) be called. A has a left subtree (B); this is the second case. The lines (8–16) of the second procedure in the code do the following in order:

  1. The left of X takes the old left of A: X->left_child = B; the flag is carried over as FALSE.
  2. The right of X points to A and is TRUE: the successor of X is A.
  3. A->left_child = X, A->left_thread = FALSE.
  4. The left flag of X is FALSE; the predecessor of X is searched for. p = X->left_child = B. The right flag of B is FALSE, go right: p = E. The right flag of E is TRUE, stop.
  5. E->right_child = X: the right thread of E points to X instead of A.

The resulting sequence is D B E X A C. X has been inserted between the B subtree and A.

The procedure inpred can be used for another job as well: starting from the header and moving from predecessor to predecessor until we return to the header traverses the tree backwards in inorder. This is taken up in the exercises. The predecessor of the header is the last node in inorder: the left flag of the header is FALSE, its left pointer is the root, and going right and right from the root reaches the rightmost node.

12.4.6Freeing the tree

In a C program, every block obtained with malloc must be returned with free when it is no longer needed. Blocks that are not returned stay in memory until the program ends. This is called a memory leak. In a long-running program a leak slowly exhausts memory. A threaded tree is freed by a traversal too:

void threaded_tree_free(thread_ptr L) {
  thread_ptr p = insucc(L), next;
  while (p != L) {
    next = insucc(p);  // find the successor first
    free(p);                           // then free the node
    p = next;
  }
  free(L);                             // the head last
}

The order matters. Reading the fields of a node after it has been returned with free means reading freed memory, which is undefined behavior. So the successor is found first and written into next, and only then is the node freed. The successor procedure reads only the fields of p and of the nodes in its right subtree. These nodes have not been freed yet, because they come after p in inorder. The header is freed last; the stopping condition of the traversal looks at its address.

All the code in these notes was tested with a wrapper that counts calls to malloc and free. The code from the slides and the additional procedures of these notes were run in a single driver: 32 malloc and 32 free calls were counted; in the detailed test both numbers were 2116. There is no leak.

12.4.7Code quality

The procedures of a threaded tree are short but error-prone. They illustrate a few principles of good code concretely.

Where to put the NULL check. insert_right does not check whether parent or child is NULL. This is not an oversight but a design decision. The reasoning given in the lecture is this: insert_right is written not to be used on its own but inside another procedure; the NULL check should be made in the procedure that uses it. For example, a procedure that inserts into a threaded binary search tree first finds whether the new value is to be inserted to the right or to the left. In place of the single assignment of an ordinary tree, it calls insert_right or insert_left. At that point parent is already a real node. But if the procedure is to be part of a library and anyone can call it directly, the check should go into the procedure. If no check is made, this should be written in the comment: "parent and child must not be NULL". A defensive wrapper for a general-purpose procedure can be written like this:

#include <assert.h>
void insert_right_checked(thread_ptr parent, thread_ptr child) {
  // parent and child must not be NULL; child must not be in a tree yet
  assert(parent != NULL && child != NULL);
  insert_right(parent, child);
}

assert stops the program, with the file name and line number, if its condition is false. It catches programmer errors early and is very valuable during testing. It is removed in a build compiled with NDEBUG defined; so it is used not for errors that user input could cause but for situations of the "this must never happen" kind. For user errors, returning an error code is more appropriate.

Comments. A comment should say what the code intends to do and should not repeat the code itself.

/* BAD: repeats the code */
if (!child->right_thread)  // right thread FALSE?
/* GOOD: states the intent */
if (!child->right_thread)  // did parent have a subtree?

A comment like "is the right thread FALSE" tells the reader nothing new; the same information is written in the code. "Does the parent have a subtree" states the intent. With intent and code side by side, the reader can compare the two and say: "what it wants to do is right, but the code is wrong." Debugging becomes easier this way. The lecture stresses this point: a later reader should not say "I already know that"; comments should say something different from what the code says.

One procedure. It was possible to write a separate procedure for each case: insert_right_no_subtree, insert_right_with_subtree, insert_left_no_subtree, insert_left_with_subtree. That would fragment the code; the user would have to decide each time which procedure to call. Reducing four procedures to two without adding complexity is good. But the opposite extreme must be avoided as well. Squeezing all the cases into one procedure with nested ifs produces unreadable code. In that situation separate procedures are better. The success of insert_right comes from defining the common work of the two cases in a common form: copying the thread flag from the parent covers both cases in a single assignment. The method can be summarized like this: first analyze the three or five different cases; then determine the name, return value, and parameters of the procedure; write the common work in a common form. The result is simple, readable, and easily maintained code. The lecture regards these principles as the foundation of software engineering and reminds us that learning them takes years.

Vigilance. When writing threaded tree code one must ask on every line: "I am doing this, but am I doing it correctly?" The code for Case 1 is flawless for Case 1 and silently corrupts the tree in Case 2. After the first six assignments of insert_right the tree looks correct, but one thread is still wrong. Such errors are caught only by trying every case separately and by traversing both forward and backward.

12.5Gains, costs, and a complexity summary

What a threaded tree gives and takes away can be collected in two lists. Gains: the traversal is done without a stack and with O(1) extra memory; the move from any node to its successor or predecessor takes at most O(h) and amortized O(1) within a traversal; the empty fields are not wasted. Costs: two flags are kept in every node; insertion and deletion become more intricate; every procedure that touches the tree has to respect the threads. Table 12.13 gives the costs of the procedures of this chapter together.

Table 12.13: Complexity summary. n is the number of nodes and h is the height of the tree.
OperationTimeExtra memoryDescription
insuccO(h) worst caseO(1)O(1) if there is a right thread
inpredO(h) worst caseO(1)O(1) if there is a left thread
tinorderΘ(n)O(1)at most 2n + 1 pointers; no stack or recursion
threaded preorder traversalΘ(n)O(1)with the same threads
insert_right / insert_leftO(h)O(1)successor or predecessor search; O(1) in Case 1
threaded_tree_freeΘ(n)O(1)freeing by traversal
Morris traversal (flagless)Θ(n)O(1)temporary threads; the tree changes during the traversal
recursive inorder (for comparison)Θ(n)O(h)call stack

12.6Common mistakes

  1. Treating a pointer as a real child without looking at the flag. In a threaded tree no pointer is NULL. A loop that descends until NULL never stops; it goes around the ring through the threads and the head. Every descent is checked with left_thread or right_thread.
  2. Forgetting the header node. In a tree without a header, the left thread of the first node and the right thread of the last node are left dangling. If NULL is written into them, the traversal procedures need special cases; if nothing is written, garbage values are followed.
  3. Not updating the left thread of the successor in the second case of right insertion. Forward traversal still gives the right result and the bug stays hidden; a procedure that looks for a predecessor or traverses backwards goes to the wrong node.
  4. Writing child->right_thread as a constant TRUE. In the second case the right subtree of the parent is treated as a thread, and the left part of that subtree drops out of the traversal. In the example, E is lost.
  5. Forgetting the left_thread of the header in an empty tree. In an empty tree the left of the header is itself and its flag is TRUE. A search that takes L->left_child for the root without looking at this flag reads the data of the header as if it were a real value.
  6. Mixing up upper and lower case. C is case-sensitive: parent->Right_child or parent->Right_thread does not compile, because the field of the structure is right_child. Note also that the threaded structure uses left_child while the ordinary structure uses left.
  7. Breaking the order of the assignments. If the line parent->right_child = child is written before child->right_child = parent->right_child, the old successor of the parent is lost and the child points to itself.
  8. Calling free first when freeing the tree. If the successor is looked up after the node has been freed, freed memory is read. First the successor is found, then the node is freed.

12.7Exercises and solutions

12.7.1Drawing the threads of a tree

Question. Draw the threads of the tree A(B(D, E), C(–, F)); how many threads are there?

Solution. The inorder sequence is D B E A C F. The tree has 6 nodes; by Theorem 12.1 there are 6 + 1 = 7 empty fields, that is, 7 threads. The threads were given one by one in Example 12.2: D → head, D → B, E → B, E → A, C → A, F → C, F → head. Two of them go to the head. The solution was also checked with a program that builds the tree and counts the flags.

12.7.2Finding the predecessor

Question. Write the procedure inpred that finds the inorder predecessor.

Solution. The procedure is the mirror image of finding the successor and was given in the section on inserting on the left. If the left flag is TRUE, the left pointer points directly to the predecessor. Otherwise we start from the left child and go right until the right flag is TRUE. In the running example the predecessor of A is found like this: p = B; the right flag of B is FALSE, p = E; the right flag of E is TRUE; the result is E.

12.7.3Traversing backwards

Question. Write the procedure that traverses a threaded tree backwards in inorder (G C F A …).

Solution. Start from the header and move from predecessor to predecessor until we return to the header:

void reverse_tinorder(thread_ptr L) {
  thread_ptr p = L;
  for (;;) {
    p = inpred(p);
    if (p == L) break;
    printf("%c ", p->data);
  }
}

The predecessor of the header is the last node (G); the predecessor of the first node (H) is the header. In the running example the output is G C F A E B I D H. The time is Θ(n) and the extra memory is O(1); the justification is the mirror image of Theorem 12.3.

12.7.4The first node of an empty tree

Question. Is it correct to insert the first node into an empty tree (only the header) with insert_left(head, x)?

Solution. It is correct. The left pointer of the header points to itself and its left flag is TRUE. insert_left carries these two over to the child: the left of the child points to the head and is a thread. The right of the child also points to the parent, that is, the head, and is TRUE. The left of the header is redirected to the child and its left flag becomes FALSE. Because the left flag of the child is TRUE, the if block does not run. In the end both threads of the single node point to the head; this is exactly the arrangement in Definition 12.3.

12.7.5Why postorder is hard

Question. Why is postorder traversal hard with threads? What extra information makes the job easier?

Solution. The postorder successor of a node depends on its parent. If the node is the right child of its parent, or the parent has no right subtree, the successor is the parent; otherwise the successor is the first node in postorder in the right subtree of the parent. In both cases we must know who the parent is and which of its children the node is. Threads point to the inorder predecessor and successor; these do not always coincide with the parent. Adding a parent pointer to each node supplies this information directly, and the postorder successor is found in a constant number of steps and one descent.

12.7.6Inserting into a threaded binary search tree

Question. Write the insertion procedure for a threaded binary search tree using insert_right and insert_left.

Solution. The search is as in an ordinary binary search tree; the only difference is that we stop when the flag of the direction to descend is TRUE. At that point insert_left is called if the sought value is smaller than the node, and insert_right if it is larger. The new node is always a leaf; so both procedures run in Case 1 and finish in constant time.

int threaded_bst_insert(thread_ptr L, char x) {
  // insert x and return 1; return 0 if present
  thread_ptr p;
  if (L->left_thread) {                  // tree is empty
    insert_left(L, new_node(x));
    return 1;
  }
  p = L->left_child;                      // start at the root
  for (;;) {
    if (x == p->data) return 0;
    if (x < p->data) {
      if (p->left_thread) break;         // no left child
      p = p->left_child;
    } else {
      if (p->right_thread) break;         // no right child
      p = p->right_child;
    }
  }
  if (x < p->data) insert_left(p, new_node(x));
  else             insert_right(p, new_node(x));
  return 1;
}

If the tree is empty (the left flag of the header is TRUE), the first node is inserted on the left of the header; the previous exercise showed that this is correct. The procedure was called in the order M F T B H P X K; then H was to be inserted once more and 0 was returned. The inorder traversal wrote B F H K M P T X and the reverse traversal wrote X T P M K H F B. The search takes O(h) and the insertion O(1); the total is O(h).

12.8Summary

  • In a binary tree with n nodes, n − 1 of the 2n pointers are filled; the remaining n + 1 fields are empty.
  • In a threaded binary tree an empty left pointer is tied to the inorder predecessor and an empty right pointer to the inorder successor. These pointers are called threads.
  • The flags left_thread and right_thread distinguish real links from threads. If the field order is chosen well, the flags fit into padding bytes on a 64-bit machine.
  • The header node collects the two dangling threads; the root is at L->left_child, and the right of the header is itself. In an empty tree the left flag of the header is TRUE.
  • Successor: if the right flag is TRUE, the right pointer directly; otherwise the leftmost node of the right subtree. The predecessor is the mirror image.
  • Threaded inorder traversal follows at most 2n + 1 pointers: Θ(n) time and O(1) extra memory. Preorder traversal can be done with the same threads; postorder needs parent information.
  • The Morris traversal traverses without flags, by building and removing threads temporarily, in O(n) time and O(1) memory; because the tree is modified during the traversal, it is not suitable for concurrent reads.
  • insert_right merges the two cases into one procedure by copying the thread flag from the parent; in the second case the child is made the predecessor of the old successor of the parent. insert_left is its mirror image.
  • Good code: a clearly defined procedure, comments that state the intent, the NULL check in the right place, and a single procedure in which common work is written in a common form.

12.9Key terms

  • null pointer
  • thread
  • threaded binary tree
  • predecessor
  • successor
  • header node
  • inorder
  • preorder
  • postorder
  • traversal
  • Morris traversal
  • call stack
  • skewed tree
  • height
  • amortized analysis
  • self-referential struct
  • binary search tree

12.10Test Yourself

  1. A binary tree with 15 nodes is being turned into a threaded tree. How many threads are built, and how many go to the header?

    Answer

    The number of empty fields is 15 + 1 = 16, so 16 threads are built. Whatever the shape of the tree, only two go to the header: the left thread of the first node and the right thread of the last node.

  2. In the running example, which node does insucc(B) return? How many times does the loop run?

    Answer

    It returns E. The right flag of B is FALSE and p becomes E. Because the left flag of E is TRUE, the loop is never entered: 0 iterations.

  3. In the running example, which node does presucc(I) return?

    Answer

    E. Because the left flag of I is TRUE, the right threads are followed: I → B. The right flag of B is FALSE; the loop ends and the right child of B, E, is returned.

  4. insert_right(E, Y) is applied to the running example. Which case is it? Where do the threads of Y point, and what is the new inorder sequence?

    Answer

    E is a leaf; it has no right subtree, so this is the first case. The left thread of Y points to E and its right thread to A, the old successor of E. The sequence becomes H D I B E Y A F C G.

  5. insert_right(A, Y) is applied to the running example. Whose thread changes?

    Answer

    This is the second case; the right subtree of A (C) becomes the right subtree of Y. The successor of Y is F, the leftmost node of C. The left thread of F points to Y instead of A. The sequence becomes H D I B E A Y F C G.

  6. In a left-skewed threaded tree of 1000 nodes, how many pointers does insucc(head) follow? How many does the whole traversal follow?

    Answer

    The first call descends from the header to the root and then, through 999 left links, to the bottom node: together with the read in line 3, 1001 pointers. The whole traversal follows 2n + 1 = 2001 pointers; this is the case that reaches the bound of Theorem 12.3 exactly.

  7. How many temporary threads does the Morris traversal build on the tree A(B(D, E), C)? What does this number equal in general?

    Answer

    Two: E → A and D → B. One thread is built for each node with a left child, and the same thread is removed later.

  8. In insert_right, if line 10 (parent->right_thread = FALSE) is deleted, in which case does the tree break?

    Answer

    In the first case, but insidiously. The flag of the parent stays TRUE. Inorder traversal still gives the right result, because the right pointer taken for a "thread" already points to the child, that is, to the successor of the parent. The other procedures skip the child. When C is inserted on the right of the tree A(B, –), the inorder traversal writes B A C; the preorder traversal writes A B and the backward traversal writes A B. C is lost. In the second case no harm is done, because the flag is already FALSE.

12.11Further reading

  • E. Horowitz, S. Sahni, and S. Anderson-Freed, Fundamentals of Data Structures in C, 2nd ed., Section 5.5. The structure of these notes, the insert_right procedure, and the layout of the header node follow the treatment there.
  • D. E. Knuth, The Art of Computer Programming, Volume 1, Section 2.3.1. Threaded trees, finding the successor, and the algorithms for insertion into a threaded tree are presented with proofs and exercises.
  • J. M. Morris, "Traversing binary trees simply and cheaply", Information Processing Letters 9(5), 1979. This is the short original paper on flagless traversal with temporary threads.

12.12References

  1. E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2nd ed., Silicon Press, 2008. Section 5.5, Threaded Binary Trees.
  2. A. J. Perlis, C. Thornton, "Symbol manipulation by threaded lists", Communications of the ACM 3(4), 1960.
  3. J. M. Morris, "Traversing binary trees simply and cheaply", Information Processing Letters 9(5), 1979.
  4. D. E. Knuth, The Art of Computer Programming, Volume 1: Fundamental Algorithms, 3rd ed., Addison-Wesley, 1997. Section 2.3.1.

Related pages: Chapter 12 slides · © Sercan Külcü. All rights reserved.