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_threadandright_threadflags and a header node. - Traversing without a stack
- Traverse in inorder and preorder with
insuccusing O(1) extra memory; trace the Morris traversal step by step. - Inserting nodes
- Merge the two cases of
insert_rightinto a single procedure and deriveinsert_leftfrom 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.
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.
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.
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.
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.
| Method | Time | Extra memory | What is remembered |
|---|---|---|---|
| Recursive | O(n) | O(h) | Open calls (the call stack) |
| Non-recursive, with a stack | O(n) | O(h) | The nodes passed while going left |
| Threaded | O(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.
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.
A threaded binary tree is a binary tree whose null pointers have been filled according to the following two rules:
- If
p->left_child == NULL, thenp->left_childpoints to the inorder predecessor of p. - If
p->right_child == NULL, thenp->right_childpoints 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.
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.
| Step | Empty field | Rule | Node pointed to |
|---|---|---|---|
| 1 | left of H | predecessor | none (head) |
| 2 | right of H | successor | D |
| 3 | left of I | predecessor | D |
| 4 | right of I | successor | B |
| 5 | left of E | predecessor | B |
| 6 | right of E | successor | A |
| 7 | left of F | predecessor | A |
| 8 | right of F | successor | C |
| 9 | left of G | predecessor | C |
| 10 | right of G | successor | none (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.
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.
| Field | Offset (bytes) | Size | Padding after it |
|---|---|---|---|
left_thread | 0 | 2 | 6 |
left_child | 8 | 8 | 0 |
data | 16 | 1 | 7 |
right_child | 24 | 8 | 0 |
right_thread | 32 | 2 | 6 |
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.
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.
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.
left_thread | left_child | data | right_child | right_thread |
|---|---|---|---|---|
TRUE | → head | – | → head | FALSE |
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.
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.
| Traversal | Rule | Order |
|---|---|---|
| inorder | left, root, right | H D I B E A F C G |
| preorder | root, left, right | A B D H I E C F G |
| postorder | left, right, root | H 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, thenp->right_childis 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 untilleft_threadisTRUE.
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:
Lmust not beNULL. In a threaded tree no pointer isNULL, so no such check is needed inside the procedure; satisfying the precondition is the caller's job. - Line 3.
preceives the right pointer ofL. 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_threadis 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 atp->left_child. The left pointer of the leftmost node is also a filled field (a thread), but its flag isTRUE. - Line 7. In both cases
ppoints to the successor, and it is returned.
The correctness of the rules follows from the definition of inorder traversal.
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.
| Call | Line | Event | p |
|---|---|---|---|
L = head | 3 | p = head->right_child; the right of the head is itself | head |
| 4 | right_thread is FALSE: the head is taken to have a real right subtree | head | |
| 5–6 | head->left_thread is FALSE, go left | A | |
| 5–6 | A->left_thread is FALSE, go left | B | |
| 5–6 | B->left_thread is FALSE, go left | D | |
| 5–6 | D->left_thread is FALSE, go left | H | |
| 7 | H->left_thread is TRUE: the loop ends, H is returned | H | |
L = A | 3 | p = A->right_child | C |
| 4 | right_thread is FALSE: A has a right subtree | C | |
| 5–6 | C->left_thread is FALSE, go left | F | |
| 7 | F->left_thread is TRUE: F is returned | F | |
L = I | 3 | p = I->right_child (a thread) | B |
| 4 | right_thread is TRUE: the loop is not entered | B | |
| 7 | B is returned | B |
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.
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.
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.
ppoints 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 thebreakin 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.
padvances 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.
| Iteration | p (before) | How it was found | p (after) | Followed | Output |
|---|---|---|---|---|---|
| 1 | head | leftmost of the right subtree (A, B, D, H) | H | 5 | H |
| 2 | H | directly through a thread | D | 1 | D |
| 3 | D | leftmost of the right subtree (I) | I | 1 | I |
| 4 | I | directly through a thread | B | 1 | B |
| 5 | B | leftmost of the right subtree (E) | E | 1 | E |
| 6 | E | directly through a thread | A | 1 | A |
| 7 | A | leftmost of the right subtree (C, F) | F | 2 | F |
| 8 | F | directly through a thread | C | 1 | C |
| 9 | C | leftmost of the right subtree (G) | G | 1 | G |
| 10 | G | directly through a thread | head | 1 | (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.
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.
p | Left flag | Right threads followed | Successor |
|---|---|---|---|
| head | F | – | A (left child) |
| A | F | – | B (left child) |
| B | F | – | D (left child) |
| D | F | – | H (left child) |
| H | T | H → D | I (right child of D) |
| I | T | I → B | E (right child of B) |
| E | T | E → A | C (right child of A) |
| C | F | – | F (left child) |
| F | T | F → C | G (right child of C) |
| G | T | G → head | head (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
LbecomesNULL. The right pointer of the last node really isNULL; 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 toL; without this test the search would follow the thread toLand 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,Lis 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.
| Iteration | L | Predecessor p | Event | Temporary threads | Output |
|---|---|---|---|---|---|
| 1 | A | E (right from B) | the right of E is empty: set the thread, go left | E→A | |
| 2 | B | D | the right of D is empty: set the thread, go left | E→A, D→B | |
| 3 | D | – | no left child: write, go right (through the thread to B) | E→A, D→B | D |
| 4 | B | D | the right of D is B: remove the thread, write, go right | E→A | DB |
| 5 | E | – | no left child: write, go right (through the thread to A) | E→A | DBE |
| 6 | A | E (right from B) | the right of E is A: remove the thread, write, go right | – | DBEA |
| 7 | C | – | no left child: write, go right (NULL) | – | DBEAC |
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:
- The parent has no right subtree. The new node is placed to the right of the parent as a leaf.
- 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 TRUEThe 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.
| Line | Assignment | Result | Reason |
|---|---|---|---|
| 1 | child->right_child = parent->right_child | D → head | The successor of the parent is now the successor of the child. It does not matter whether this successor is the head. |
| 2 | child->right_thread = TRUE | red arrow | The parent had no right subtree; the child, being a leaf, has none either. |
| 3 | child->left_child = parent | D → B | The predecessor of the child is the parent. |
| 4 | child->left_thread = TRUE | red arrow | This is a thread as well. |
| 5 | parent->right_child = child | B → D | A real link from the parent to the child. |
| 6 | parent->right_thread = FALSE | black link | The right of the parent is no longer a thread but a real child. |
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 isTRUE, and the thread status passes to the child; in Case 2 it isFALSE, 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 alreadyFALSE, so this assignment is unnecessary but harmless; in Case 1 it is needed. Writing it in both cases, instead of separating them with anif, 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.
| Line | Event | Changed field |
|---|---|---|
| 5 | The old right subtree of B goes to the right of X | X->right_child = D |
| 6 | The flag of B was FALSE; the real-link status is kept | X->right_thread = FALSE |
| 7 | The predecessor of X is B | X->left_child = B |
| 8 | red arrow | X->left_thread = TRUE |
| 9 | A real link from B to X | B->right_child = X |
| 10 | it was already FALSE; harmless | B->right_thread = FALSE |
| 11 | !X->right_thread is true: X has a right subtree | – |
| 12 | The successor of X: descend left from D and stop at E | p = E |
| 13 | The left thread of E points to X instead of B | E->left_child = X |
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
}
}insert_right | insert_left |
|---|---|
child->right_child = parent->right_child | child->left_child = parent->left_child |
child->right_thread = parent->right_thread | child->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 = FALSE | parent->left_thread = FALSE |
| left thread of the successor to the child | right thread of the predecessor to the child |
insucc: right, then left and left | inpred: left, then right and right |
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:
- The left of X takes the old left of A: X->
left_child= B; the flag is carried over asFALSE. - The right of X points to A and is
TRUE: the successor of X is A. - A->
left_child= X, A->left_thread=FALSE. - The left flag of X is
FALSE; the predecessor of X is searched for.p= X->left_child= B. The right flag of B isFALSE, go right:p= E. The right flag of E isTRUE, stop. - 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.
| Operation | Time | Extra memory | Description |
|---|---|---|---|
insucc | O(h) worst case | O(1) | O(1) if there is a right thread |
inpred | O(h) worst case | O(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_left | O(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
- Treating a pointer as a real child without looking at the flag. In a threaded tree no pointer is
NULL. A loop that descends untilNULLnever stops; it goes around the ring through the threads and the head. Every descent is checked withleft_threadorright_thread. - 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
NULLis written into them, the traversal procedures need special cases; if nothing is written, garbage values are followed. - 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.
- Writing
child->right_threadas a constantTRUE. 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. - Forgetting the
left_threadof the header in an empty tree. In an empty tree the left of the header is itself and its flag isTRUE. A search that takesL->left_childfor the root without looking at this flag reads the data of the header as if it were a real value. - Mixing up upper and lower case. C is case-sensitive:
parent->Right_childorparent->Right_threaddoes not compile, because the field of the structure isright_child. Note also that the threaded structure usesleft_childwhile the ordinary structure usesleft. - Breaking the order of the assignments. If the line
parent->right_child = childis written beforechild->right_child = parent->right_child, the old successor of the parent is lost and the child points to itself. - Calling
freefirst 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_threadandright_threaddistinguish 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 isTRUE. - 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_rightmerges 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_leftis 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
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.
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
FALSEandpbecomes E. Because the left flag of E isTRUE, the loop is never entered: 0 iterations.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 isFALSE; the loop ends and the right child of B, E, is returned.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.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.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.
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.
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 writesB A C; the preorder traversal writesA Band the backward traversal writesA B. C is lost. In the second case no harm is done, because the flag is alreadyFALSE.
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_rightprocedure, 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
- E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2nd ed., Silicon Press, 2008. Section 5.5, Threaded Binary Trees.
- A. J. Perlis, C. Thornton, "Symbol manipulation by threaded lists", Communications of the ACM 3(4), 1960.
- J. M. Morris, "Traversing binary trees simply and cheaply", Information Processing Letters 9(5), 1979.
- 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.