Data Structures and Algorithms with C · Lecture Notes
Chapter 10: Trees
Arrays, linked lists, stacks, and queues are linear structures: every element has at most one predecessor and one successor. A large share of real-world data, however, is hierarchical. A folder contains many folders, a manager has many employees, and an arithmetic operation combines the results of two sub-operations. The structure that holds such relationships naturally is the tree. These notes first define tree terminology on an example. They then define the binary tree and prove its basic results about node counts. Next they build the two memory representations of a binary tree, with an array and with pointer-linked nodes, in C. Most of the notes are devoted to traversal: preorder, inorder, and postorder traversals are written first recursively and then iteratively with a stack, and a queue is used for level-order traversal. The last sections cover short recursive procedures that copy a tree, compare two trees, and mirror a tree, and rebuilding a tree from its traversal sequences. The time and memory cost of every procedure is given with its justification.
Learning outcomes
- Using the terminology
- Show the notions of root, parent, child, sibling, ancestor, descendant, degree, level, depth, and leaf on a tree; tell degree and depth apart.
- Analyzing binary trees
- Prove that the maximum number of nodes on a level is 2i−1 and the maximum number of nodes in a tree of depth k is 2k − 1; tell perfect, complete, and incomplete trees apart; use the equality n0 = n2 + 1.
- Building the two representations
- Represent a binary tree with an array (parent ⌊i/2⌋, children 2i and 2i + 1) and with
tree_pointerlinked nodes; compare the memory cost of the two representations. - Writing traversals
- Write preorder, inorder, and postorder traversals recursively and iteratively with a stack; traverse level by level with a queue; find the output of a traversal by hand.
- Building tree procedures
- Write recursive procedures that print leaf nodes, copy a tree, check whether two trees are equivalent, and swap left and right children; delete a tree without leaving a memory leak.
- Computing the cost
- Justify the O(n) time and the O(h) memory, proportional to the depth, of each procedure; state what these bounds are for balanced and skewed trees.
10.1The tree data structure
In a linked list each node points to the next node. What would happen if a node could point to more than one next node? The list branches, and a tree emerges. This section defines the tree, lists where it is used, and shows the property that sets it apart from the more general structure, the graph.
10.1.1Definition and uses
Everyday life has many tree-shaped arrangements. In a family tree, each person has their children below them. In an organization chart, below the general manager come the managers, and below them the supervisors. The file system of a computer is also a tree: inside the root folder there are folders, and inside them other folders and files. Every file has a single parent folder. What these arrangements have in common is a single starting point at the top, and every element hanging from exactly one element above it.
In computer science the tree underlies search and sorting structures, data compression, and compilers. When a compiler reads a program, it first parses the syntax and builds the structure of the program as a tree. Code optimization and intermediate code generation work on this tree. Arithmetic expressions, decision processes, move options in games, and database indexes are also kept in trees.
A tree is a finite set of one or more nodes. One of the nodes is designated the root. The remaining nodes are partitioned into n ≥ 0 disjoint sets T1, …, Tn. Each of these sets is again a tree and is called a subtree of the root.
The definition is recursive: it defines the tree in terms of parts that are themselves trees. When the root is removed, a few smaller trees remain; when their roots are removed, still smaller trees remain. This process goes down to trees with a single node. This form of the definition explains why procedures that work on trees are naturally written recursively. A procedure does a small piece of work at the root and then calls itself for each of the subtrees. Since the subtrees are disjoint, no node is processed twice. All the traversal, copy, and comparison procedures in these notes follow this pattern.
10.1.2Trees and graphs
The most general structure made of nodes and the edges connecting them is the graph. A tree is a special kind of graph. In a tree every node other than the root has a single parent. In a graph, edges can arrive at a node from several nodes. Figure 10.1 shows the two structures side by side. In the structure on the left, B and C are below A, and D and E are below C; every node receives a single edge from above. In the structure on the right, D receives edges from both B and C. Because D has two parents, this structure is not a tree.
The single-parent condition has two important consequences. First, the path from the root to any node is unique. Second, a tree has no cycles: starting from a node and following edges, one cannot return to the same node. In a tree with n nodes, exactly one edge enters each node other than the root, so the number of edges is n − 1. The relations on the number of nodes of binary trees also rest on this count.
Applying tree procedures to a graph. In a tree a node is reached by a single path, so no visited mark is needed. In a graph, if no mark is kept, nodes are processed again and again; if there is a cycle, the procedure never ends.
10.2Terminology
Most tree terms come from the family tree: parent, child, sibling, ancestor, grandchild. The remaining terms (degree, level, depth) describe nodes and the tree numerically. This section defines all the terms on a single example tree. Figure 10.2 shows this tree: thirteen nodes, four levels. The small numbers at the upper right of the nodes are the degrees of the nodes.
10.2.1Parent, child, sibling, ancestor, and descendant
The node at the very top of the tree, with no parent, is the root. In the example tree the root is A. A node that has subtrees is the parent of the roots of those subtrees. The roots of the subtrees are the children of that node. B is the parent of E and F; E and F are the children of B. Children of the same parent are siblings of one another: E and F are siblings, and H, I, and J are siblings too. The terminology extends to grandparent and grandchild, as in a family tree. D is the grandparent of M, because the parent of the parent of M, H, is D.
The ancestors of a node are all the nodes on the path from the root to that node. The ancestors of M are A, D, and H. The root is not a descendant of any node; the root has no ancestors. All the nodes in the subtree of a node are its descendants. The descendants of B are E, F, K, and L. Children of children are grandchildren: E, F, G, H, I, and J are the grandchildren of A. The two definitions are inverses of each other: if X is an ancestor of Y, then Y is a descendant of X. This relation matters in traversal procedures. A recursive procedure that processes a node also processes all of its descendants, and never touches its ancestors.
10.2.2Degree, leaf, level, and depth
The degree of a node is the number of subtrees of that node, that is, its number of children. The degree of A is 3, of B 2, of C 1, and of F 0. A node of degree 0 is called a leaf or a terminal node. The leaves of the example tree are K, L, F, G, M, I, and J. Nodes with at least one child are internal nodes: A, B, C, D, E, and H.
The level of a node is numbered starting from the root. In this course the root is at level 1; the level of a node is one more than the level of its parent. B, C, and D are at level 2, E, F, G, H, I, and J at level 3, and K, L, and M at level 4. Two numbers are also defined for the tree itself. The degree of the tree is the largest of the node degrees; in the example tree it is 3 (A and D). The depth of the tree is the largest level number among the nodes; in the example tree it is 4. Figure 10.3 shows the two numbers in the same drawing.
Degree and depth answer different questions. Degree measures how widely the tree branches, and depth how far down it goes. A tree that stretches out like a chain has degree 1 and depth equal to the number of nodes. A tree with a hundred leaves attached directly under the root has degree 100 and depth 2. The memory cost of traversal procedures depends on the depth; in binary trees the degree is at most 2 anyway.
All the terms for node H in Figure 10.2 are as follows. The parent of H is D; its only child is M. Its siblings are I and J. Its ancestors, starting from the root, are A and D. Its only descendant is M. Its degree is 1, so H is an internal node. Its level is 3: A is at level 1, D at level 2, and H at level 3. The subtree that takes H as the root has two nodes (H and M) and depth 2.
Giving degree and depth with the same definition, as in "the depth of the tree is the largest of the node degrees". This sentence defines the degree of the tree, not its depth. In the example tree the two values are 3 and 4; in a chain they are 1 and n. In exam questions the two are asked separately and cannot be used in place of each other.
10.2.3Definitions of depth: books count differently
The notions of level and depth shift from source to source. The main source of this course is the book by Horowitz, Sahni, and Anderson-Freed. In this book the root is at level 1 and the depth of the tree is the largest level, that is, the number of nodes on the path from the root to the farthest leaf. The books by Cormen et al. (CLRS) and by Sedgewick take the depth of the root to be 0. In those books the height of the tree is the number of edges on the path from the root to the farthest leaf. For the same tree the two definitions differ by one. Table 10.1 compares the values in the example tree.
| Concept | This course (Horowitz–Sahni) | CLRS / Sedgewick |
|---|---|---|
| Level of the root | 1 | 0 |
| Level of M | 4 | 3 |
| Depth / height of the tree | 4 (depth) | 3 (height) |
| Tree with a single node | 1 | 0 |
| Empty tree | 0 | −1 |
Neither of the two definitions is right and the other wrong; only the thing measured differs. One counts nodes, the other edges. The number of edges on a path is always one less than the number of nodes. So the formulas shift by one too: in this course a binary tree of depth k has at most 2k − 1 nodes; written with height, the same bound is 2h+1 − 1. When using a formula in an exam or a source, one should first check which definition applies.
In these notes depth is also used as a function: depth(NULL) = 0, and the depth of a tree with a single node is 1. The depth of a non-empty tree is one more than the larger of the depths of its two subtrees. This definition turns directly into a C function:
int depth(tree_pointer L) { /* empty tree 0, single node 1 */
if (!L) return 0;
int s = depth(L->left_child);
int r = depth(L->right_child);
return 1 + (s > r ? s : r);
}The function first catches the empty tree and returns 0. For a non-empty tree it computes the depths of the two subtrees recursively and adds 1 to the larger. The added 1 is the root itself. Since it visits every node once, its time is O(n). In tests with the binary trees from the slides the function gave the same values as hand computation; for the empty tree it returned 0.
10.3The binary tree
In a general tree the number of children of a node is unbounded. This flexibility creates a problem in memory: it is not known in advance how many pointer fields to reserve in each node. When the number of children is limited to at most two, both the memory layout becomes fixed and the procedures become simpler. This section defines the binary tree and proves the relations between its number of nodes and its depth.
10.3.1Definition
A binary tree is a finite set of nodes. This set is either empty or consists of a root and two disjoint binary trees, called the left subtree and the right subtree.
Two details of the definition differ from the general tree. First, a binary tree may be empty; in the definition of a general tree there is at least one node. Thanks to the empty tree, the case "there is no left subtree" is expressed as "the left subtree is empty". All procedures also end with a single base case, the empty tree. Second, left and right are distinguished. In a node with one child, it matters whether the child is on the left or on the right. Consider two trees with root A and a single child B: in one, B is on the left; in the other, on the right. As general trees they are the same tree; as binary trees they are two different trees. So node degrees can be 0, 1, or 2, but for a node of degree 1 the direction of the child also carries information.
There is an inclusion relation among these sets: every binary tree (other than the empty one) is a tree, and every tree is a graph. Figure 10.4 shows two binary trees. In the tree on the left, every node has only a left child; this kind of tree is called a skewed tree. The tree on the right has four levels and the nodes are distributed evenly over the levels.
The two trees in the figure have the same depth; their numbers of nodes are 4 and 11. Very different numbers of nodes can fit in the same depth. Since depth determines the memory cost of traversal procedures, the question "what are the smallest and largest possible depths of a tree with n nodes?" is important. The next two subsections answer it.
10.3.2Maximum number of nodes on a level and in a tree
In a binary tree every node has at most two children, so the number of nodes at each level is at most twice that of the previous one. This observation gives two bounds.
(i) A binary tree has at most 2i−1 nodes on level i (i ≥ 1). (ii) A binary tree of depth k has at most 2k − 1 nodes (k ≥ 1).
Proof. (i) By induction on i. The base case is i = 1: at level 1 there is only the root, and 20 = 1. For the induction step, assume that level (i − 1) has at most 2i−2 nodes. Every node at level i is a child of a node at level (i − 1), and every node has at most two children. So level i has at most 2 · 2i−2 = 2i−1 nodes.
(ii) In a tree of depth k the nodes are distributed over levels 1 to k. (i) gives the bound for each level. The total number of nodes is at most
Σi=1..k 2i−1 = 20 + 21 + … + 2k−1 = 2k − 1
The last equality is a geometric sum: writing the sum as S, we get 2S − S = 2k − 20. ∎
The course textbook calls this result a "lemma". A lemma is a small statement whose truth is easy to see and which is used as a step in the proof of a larger theorem. Figure 10.5 shows the counts level by level in a tree of four levels: 1, 2, 4, and 8 nodes, 15 in total. If the depth were 5, 16 more nodes would be added at the fifth level, making 31 in total.
10.3.3Perfect and complete binary trees
Trees that reach the bound of Theorem 10.1 get a special name. There are also trees that come closest to this bound, in which the last level may be incomplete. Because of the similarity of their names, the two notions are often confused.
A binary tree of depth k with exactly 2k − 1 nodes is called a perfect binary tree: all its levels are full. The nodes of a perfect tree are numbered 1, 2, 3, … starting from the root, from left to right at each level. The n nodes of a binary tree may match one to one the nodes numbered 1 to n of the perfect tree of the same depth. In this case the tree is called a complete binary tree.
The numbering rule is simple: if the number of a node is i, the number of its left child is 2i and that of its right child is 2i + 1. The root is 1; the children of the root are 2 and 3; the children of 2 are 4 and 5, and those of 3 are 6 and 7. A complete tree is the tree obtained when these numbers are used from 1 to n without gaps. In everyday words: all levels except the last are full, and the nodes of the last level are arranged from left to right with no gaps.
The tree on the right in Figure 10.6 has ten nodes, but it is not complete. The node numbered 5 has no left child, only a right child. So the numbers are 1–9 and 11; 10 is skipped. In the middle tree, however, 5 has only a left child and the numbers run from 1 to 10 without a break. Every perfect tree is also complete; the converse is not true.
The complete tree matters for two reasons. First, a complete tree fits into an array with no gaps: the node numbered i is put in cell i of the array and no cell is left empty. Second, among binary trees with n nodes, the complete tree has the smallest depth. The heap structure is built on these two properties.
Confusing "complete tree" with "a tree in which every node has either 0 or 2 children". The second notion is called a full binary tree; a tree with all levels full is a perfect binary tree. In the middle tree, node 5 has a single child, yet the tree is complete. Whether a tree is complete is seen from the node numbers: is every number from 1 to n used?
10.3.4Relations between depth and node count
In a binary tree of depth k, every level has at least one node; otherwise the depth would not be k. So the number of nodes is at least k. By Theorem 10.1 it is at most 2k − 1. Written together:
k ≤ n ≤ 2k − 1
This inequality can also be written in terms of depth. From the right side we get n + 1 ≤ 2k, that is, lg(n + 1) ≤ k; since k is an integer, ⌈lg(n + 1)⌉ ≤ k. The left side is k ≤ n. As a result
⌈lg(n + 1)⌉ ≤ k ≤ n
The lower bound is reached by the complete tree: the depth of a complete tree is ⌈lg(n + 1)⌉ = ⌊lg n⌋ + 1. The upper bound is reached by the skewed tree: there is a single node at each level and the depth is n. For example, the depth of a binary tree with 20 nodes can be between 5 and 20; the depth of a complete tree with 20 nodes is ⌈lg 21⌉ = 5. These two extremes are the source of all the cost results of the form "O(lg n) in a balanced tree, O(n) in a skewed tree".
The second relation on node counts ties the leaves to the nodes with two children. In a binary tree, let the numbers of nodes of degree 0, 1, and 2 be n0, n1, and n2 respectively.
In every non-empty binary tree n0 = n2 + 1: the number of leaves is one more than the number of nodes with two children.
Proof. The nodes are counted in two ways. Since the degree of every node is 0, 1, or 2, n = n0 + n1 + n2. Exactly one edge enters each node other than the root from above; the number of edges is n − 1. The edges can also be counted as they leave the nodes: one edge leaves a node of degree 1 and two leave a node of degree 2. Hence n − 1 = n1 + 2n2. Subtracting the second equation from the first gives 1 = n0 − n2, that is, n0 = n2 + 1. ∎
Figure 10.7 checks the equality with an example. The two nodes with one child (F and G) do not affect the result: adding a node with one child to a chain changes neither the number of leaves nor the number of nodes with two children. A new leaf is gained only by adding a second child to an existing node; this operation also increases n2 by one.
The theorem has an important consequence for the C implementation. In the linked representation each node carries two pointer fields; in n nodes there are 2n fields in total. Of these, n − 1 point to an edge, that is, to a child. The remaining 2n − (n − 1) = n + 1 fields are NULL. In the eleven-node example, 10 of the 22 fields are filled and 12 are empty. There are more empty pointers than filled ones. If these empty fields are used to point to the previous and next node in inorder, a threaded binary tree is obtained. The same number also gives how many times the recursive traversals are called with NULL.
10.4Representing a binary tree in memory
A binary tree can be kept in memory in two ways. In the first, the nodes are placed in an array according to their numbers; the parent and children are found by index arithmetic. In the second, each node is a separate struct and is linked to its children by pointers. This section builds both representations in C code and discusses when to choose which.
10.4.1Array representation
The numbering of a complete tree directly gives an array layout: the node numbered i is put in the cell with index i of the array. To keep the formulas simple, indices start at 1; cell 0 of the C array is not used. The parent and child indices are computed as follows:
- parent(i) = ⌊i/2⌋ (
parent(i)in the code). If i = 1, the node is the root and has no parent. - left_child(i) = 2i. If 2i > n, there is no left child.
- right_child(i) = 2i + 1. If 2i + 1 > n, there is no right child.
#define MAX_NODES 63 /* 2^k - 1 */
char tree[MAX_NODES + 1]; /* [0] unused */
int n; /* node count */
int parent(int i) { return i / 2; }
int left_child(int i) { return 2 * i; }
int right_child(int i) { return 2 * i + 1; }
/* has a child? left_child(i) <= n */MAX_NODES is the largest number of nodes the array can hold. To be able to hold a tree of depth k in any shape, 2k − 1 cells must be reserved; here 63 is chosen for k = 6. The size of the array is MAX_NODES + 1, because cell 0 is left empty. n holds the current number of nodes. The three functions give their results with a single arithmetic operation: since in C the quotient of two positive integers is rounded down, i / 2 is already ⌊i/2⌋. Whether a child exists is found by comparing the index with n: if left_child(i) <= n, the left child exists.
The correctness of the formulas can be seen from the numbering. Let the level of node i start at 2j. The next level starts at 2j+1, and every node to the left of i gives two children there. The number of the left child is 2j+1 + 2(i − 2j) = 2i, and that of the right child is 2i + 1. Both 2i and 2i + 1 give i when divided by two and rounded down.
| i | tree[i] | parent(i) | left_child(i) | right_child(i) |
|---|---|---|---|---|
| 1 | A | — (root) | 2 (B) | 3 (C) |
| 2 | B | 1 (A) | 4 (D) | 5 (E) |
| 3 | C | 1 (A) | 6 (F) | 7 (G) |
| 4 | D | 2 (B) | 8 (H) | 9 (I) |
| 5 | E | 2 (B) | 10 (J) | — (11 > 10) |
| 6 | F | 3 (C) | — (12 > 10) | — |
| 7–10 | G, H, I, J | 3, 4, 4, 5 | — | — |
The values in Table 10.2 were produced with a small test program for the code. The left child of E, number 5, is J, number 10; the right child, which would be cell 11, does not exist because 11 exceeds n = 10. The nodes numbered 6 and above are leaves. Whether a node is a leaf is also found by the index alone: if 2i > n, then i is a leaf. In the ten-node tree the leaves are the nodes 6 to 10; in general, in a complete tree the nodes from ⌊n/2⌋ + 1 to n are leaves.
Putting the root in cell 0 and using the 1-based formulas. If the root is at 0, left_child(0) = 0 gives the root again; the tree folds onto itself. In the 0-based layout the formulas are 2i + 1, 2i + 2, and ⌊(i − 1)/2⌋. One of the two layouts must be chosen and the formulas written accordingly; in this course cell 0 is left empty.
10.4.2Wasted memory in the array
The array representation can be used for any binary tree: the tree is thought of as embedded in the perfect tree of the same depth, and the cells of nonexistent nodes are left empty. But these empty cells waste memory. Figure 10.8 compares two extreme cases.
In a complete tree there is either no wasted memory or it is limited to a few cells at the last level. The further the tree is from complete, the more empty cells there are. The worst case is the skewed tree. In a left-skewed tree every node is the left child of the previous one; the numbers double: 1, 2, 4, 8, … A left-skewed tree with k nodes needs 2k − 1 cells and uses only k of them. For k = 5, 26 of the 31 cells are empty. If k = 30, more than a billion cells would be needed; for a list of thirty nodes this is unacceptable. The array representation also causes trouble when the tree changes: inserting or deleting a node in the middle requires moving the whole subtree below it to other indices.
The course instructor sums up the situation like this: storage and access are the two main subjects of computer science; if the tree is a complete binary tree and no insertions or deletions will be made, implementing it with an array is appropriate. In every other case the tree is kept in the linked representation.
10.4.3Linked representation
In the linked representation each node is a struct that carries two pointers along with its data. The left pointer points to the root of the left subtree and the right pointer to the root of the right subtree. If the subtree is empty, the pointer is NULL. The definition used in this course is:
typedef struct tree *tree_pointer;
struct tree {
tree_pointer left_child; /* left subtree */
char data;
tree_pointer right_child; /* right subtree */
};The first line gives the pointer type pointing to struct node the name tree_pointer. This line can be written before struct node is defined, because C allows defining a pointer to a structure without knowing its contents. Inside the structure there are two fields of type tree_pointer; the structure points to objects of its own kind. Such structures are called self-referential structures. The node structure of the linked list had a single link field; here there are two. The tree itself is represented by the address of the root node: the declaration tree_pointer root; is a tree variable. root == NULL means the empty tree.
NULL pointers. Five nodes have ten pointer fields; four are filled and six (n + 1) are NULL.The nodes are allocated one by one from heap memory with malloc and may land anywhere in memory. The tree structure is built by pointers alone. Table 10.3 gives one possible memory view of the tree in Figure 10.9. The addresses are chosen as examples; real addresses change on every run. What matters here is that the order of the nodes has nothing to do with the shape of the tree.
| Address | left_child | data | right_child |
|---|---|---|---|
| 0x1040 | NULL | 'E' | NULL |
| 0x10a0 | 0x2020 | 'B' | 0x1040 |
0x1f00 (root) | 0x10a0 | 'A' | 0x2060 |
| 0x2020 | NULL | 'D' | NULL |
| 0x2060 | NULL | 'C' | NULL |
The space a node occupies in memory depends on the compiler and the machine. On a 64-bit machine every pointer is 8 bytes and data is 1 byte. To align the second pointer to an address that is a multiple of 8, the compiler adds 7 bytes of padding after data. In the Windows x86-64 build used for testing, sizeof(struct node) came out as 24 bytes: two pointers of 16 bytes, 1 byte of data, and 7 bytes of padding. If the field order were left_child, right_child, data, the padding would move to the end and the size would again be 24. A tree with n nodes takes up the space of n nodes; the shape of the tree does not affect memory. Unlike in the array representation, a skewed tree takes as much space as a balanced one.
10.4.4Allocating nodes and releasing the tree
For each new node the same three jobs are done: memory is allocated, it is checked that the allocation succeeded, and the child pointers are set to NULL. Gathering these jobs in a single function both shortens the code and prevents the errors that a forgotten check would cause. get_node from the slides and its inverse tree_free are the following:
tree_pointer get_node(void) { /* new node */
tree_pointer p = malloc(sizeof *p);
if (p == NULL) {
fprintf(stderr, "Out of memory!\n");
exit(EXIT_FAILURE);
}
p->left_child = p->right_child = NULL;
return p;
}
void tree_free(tree_pointer L) { /* postorder */
if (!L) return;
tree_free(L->left_child);
tree_free(L->right_child);
free(L);
}The first line of get_node asks for room for one node with malloc(sizeof *p). Writing sizeof *p gives the size of the type that p points to; the expression stays correct even if the type name changes. If malloc cannot find space, it returns NULL. In that case the function writes a message to stderr and ends the program with exit(EXIT_FAILURE). This is enough for homework and exam programs; in a large program NULL is returned to the caller and the decision is made there. The memory malloc gives is not cleared; the fields hold random values. So the two child pointers are explicitly set to NULL. The expression p->left_child = p->right_child = NULL; works from right to left: first NULL is assigned to right_child, and the value of that assignment is assigned to left_child. The caller fills in the data field.
tree_free returns all the nodes of the tree to the heap. The order matters: first the left subtree and then the right subtree are freed, and the root is released last. If the root were released with free first, reading the fields L->left_child and L->right_child would mean accessing released memory. This is undefined behavior. The read sometimes "works" and sometimes gives garbage; either way, the subtrees either leak or the program crashes. This order, which leaves the root for last, is postorder traversal itself. Since the function visits each node once, it runs in O(n) time. Called with an empty tree it does nothing; tree_free(NULL) is safe.
All the C code in these notes was also run with a counting malloc/free wrapper. At the end of every test the numbers of allocated and released nodes came out equal; no test left a leak. For example, in the traversal tests 53 nodes were allocated and 53 nodes were returned by the tree_free calls.
Deleting a tree by releasing only the root node: free(root);. This line returns a single node; the addresses of the remaining n − 1 nodes were inside the root and can no longer be read. These nodes stay in memory until the program ends. In a long-running program this much memory is lost at every tree deletion. The right way is a procedure such as tree_free that visits all the nodes in postorder.
10.4.5Array or linked representation?
The strengths and weaknesses of the two representations complement each other. Table 10.4 summarizes the comparison.
| Criterion | Array | Linked representation |
|---|---|---|
| Extra space per node | None (no pointer fields) | Two pointers |
| Total memory | 2k − 1 cells; no loss in a complete tree, very large in a skewed tree | n nodes in every shape |
| Access to the parent | O(1): ⌊i/2⌋ | Not directly (a parent field can be added if needed) |
| Access to a child | O(1): 2i, 2i + 1 | O(1): pointer |
| Insertion and deletion | Subtrees may have to be moved | Only pointer assignments |
| Where suitable | A complete tree whose shape does not change (e.g., a heap) | Any tree whose shape changes |
In short, the rule is this: if the tree is complete and fixed, use an array; for a tree whose shape changes, choose the linked representation. For example, if the computers in a network are fixed and will not be added or removed later, the connection tree can be kept in an array. A heap makes full use of the speed of the array, because it inserts and deletes in a way that always keeps it complete. Search trees, on the other hand, can grow in any direction with insertion; they are kept in the linked representation. The only weakness of the linked representation is access to the parent. If we need to go up from a node, a third pointer, a parent field, is added to the node; this costs 8 more bytes per node and one more assignment at every insertion.
10.4.6Converting a general tree to a binary tree
In a general tree the number of children of a node varies. A has three children while F has none. Reserving, in a fixed-field struct, as many pointers per node as "the most children a node can have" leaves most pointers empty. In a tree of n nodes with degree d, only n − 1 of the nd fields are filled. The solution is the left-child right-sibling representation: each node carries only two links. The first points to the first (leftmost) child of the node, the second to the sibling immediately to its right.
struct gnode {
char data;
struct gnode *child; /* = left */
struct gnode *sibling; /* = right */
};This structure has the same form as a binary tree node: child takes the place of the left pointer and sibling that of the right pointer. So every general tree can be stored as a binary tree, and all the procedures written for binary trees can be applied to it. Figure 10.10 shows the conversion in two steps.
NULL.The conversion is done as follows. For each node the link to the first child is kept and the links to the other children are removed. Then the children of the same parent are tied to one another in a chain from left to right. The first child of B is E; the sibling of E is F. The first child of A is B; the sibling of B is C, and the sibling of C is D. In the binary tree, B becomes the left child of A, C becomes the right child of B, and D becomes the right child of C. Since the root has no sibling, the right link of the root is always NULL.
The conversion has two consequences for traversal. The preorder of the binary tree is the same as the preorder of the general tree: both give A B E K L F C G D H M I J. The inorder of the binary tree equals the postorder of the general tree: K L E F B G C M H I J D A. The reason for the second is this: in the binary tree, the left subtree of a node is all its descendants in the general tree. Inorder traversal first writes the left subtree, that is, all the descendants, and writes the node itself after them. The right subtree is the siblings, and they come after the node. This is the rule "children first, then itself" in the general tree. Both equalities were also checked with a Python script.
10.5Recursive traversals
Visiting all the elements of a data structure once each in a particular order is called traversal. In an array and a linked list the traversal order is natural: from start to end. In a binary tree, two directions are available from each node, and the question "which first?" has more than one answer. This section counts the possible orders, writes three of them in C, traces the code step by step, and derives its cost.
10.5.1Six traversal orders
At a node there are three things to handle: the data of the node (V), the left subtree (L), and the right subtree (R). A traversal decides in which order to process these three and repeats the same decision in every subtree. Three items have 3! = 6 different orders. Table 10.5 lists them all.
| Order | Name |
|---|---|
| Left – Data – Right (L-V-R) | inorder |
| Left – Right – Data (L-R-V) | postorder |
| Data – Left – Right (V-L-R) | preorder |
| Right – Data – Left (R-V-L) | reverse inorder |
| Right – Left – Data (R-L-V) | reverse postorder |
| Data – Right – Left (V-R-L) | reverse preorder |
The three orders in which the left is traversed before the right are the standard ones, and they take their names from the position of the root. If the root is processed before the subtrees, it is preorder; if between the two subtrees, inorder; if after both, postorder. The name preorder in the C code comes from this term. The remaining three orders are the right-to-left mirrors of the standard orders. If an application requires it, they are used too.
10.5.2The expression tree and three notations
The names of the traversal orders are familiar from arithmetic expressions. An expression tree is a binary tree whose internal nodes are operators and whose leaves are operands. Each operator node is applied to the values of its two subtrees. Figure 10.11 shows the tree of the expression ((((A / B) * C) * D) + E). Since the last operator applied is +, it is the root; its left subtree is ((A / B) * C) * D and its right subtree is E.
When this tree is traversed in the three standard orders, the three well-known notations of the expression appear:
- Inorder:
A / B * C * D + E. This is the infix notation. The tree has no parentheses; when writing infix, parentheses are added around each subtree and ((((A/B)*C)*D)+E) is recovered. - Preorder:
+ * * / A B C D E. This is the prefix notation. - Postorder:
A B / C * D * E +. This is the postfix notation.
Prefix and postfix notations need no parentheses: the order of the operators determines the order of computation unambiguously. Compilers first convert the expressions in source code into such a tree. Postfix notation is evaluated with a stack in a single left-to-right pass: when an operand arrives it is pushed onto the stack; when an operator arrives, two values are taken from the stack, the operation is performed, and the result is pushed back. The postorder traversal of the tree produces exactly this order.
10.5.3Three traversals of the same tree
To find the output of a traversal by hand, the rule is repeated in every subtree. On the tree A…L with twelve nodes the three traversals are found as follows. In the tree, the left child of A is B and the right child is F. B has no left child; its right child is C. The children of C are D and E; the children of D are G and H. E has only a right child, I; the children of I are J and K. F has only a left child, L. Figure 10.12 shows the tree numbered in inorder.
- Preorder (V-L-R). First the root A is written. Then the whole left subtree: B, followed by the subtree of C, the right child of B (C, D, G, H, E, I, J, K). Last the right subtree: F, L. Output:
ABCDGHEIJKFL. - Inorder (L-V-R). Start from B, the left subtree of A. Since the left of B is empty, B is written first. Then the right subtree of B is traversed in inorder: G, D, H, C, E, J, I, K. Then A is written, and last the subtree of F: L, F. Output:
BGDHCEJIKALF. - Postorder (L-R-V). In every subtree the root comes last. G, H, D; then J, K, I, E; then C, B; then L, F; and last A. Output:
GHDJKIECBLFA.
In the three outputs the relative order of the leaves (G, H, J, K, L) is the same. The traversals differ only in where the internal nodes are placed among the leaves. This observation helps in checking an output found by hand. The first letter of the preorder output and the last letter of the postorder output are always the root.
10.5.4The traversal procedures
The recursive definition of traversal turns into C code almost word for word. For preorder traversal one says "if the tree is not empty, write the root, traverse the left subtree in preorder, traverse the right subtree in preorder":
void preorder(tree_pointer L) {
if (L) {
printf("%c", L->data);
preorder(L->left_child);
preorder(L->right_child);
}
}The inorder and postorder procedures have the same skeleton; only the place of the printf line changes:
void inorder(tree_pointer L) {
if (L) {
inorder(L->left_child);
printf("%c", L->data);
inorder(L->right_child);
}
}void postorder(tree_pointer L) {
if (L) {
postorder(L->left_child);
postorder(L->right_child);
printf("%c", L->data);
}
}The three procedures read line by line as follows. The test if (L) is true if L points to a non-empty tree. This single test does two jobs. First, a procedure called with an empty tree returns without doing anything; inorder(NULL) is safe. Second, it is the stopping condition of the recursion: each call descends into a subtree, the call after a leaf is made with NULL, and the chain stops there. printf("%c", L->data) writes the data of the node; L->data is shorthand for (*L).data. The two recursive calls traverse the left and right subtrees by the same rule. If printf is before the calls, we get preorder; if between them, inorder; if after, postorder.
The course instructor often warns about these codes: the tree pointer can be NULL, and most students do not pay attention to it. The test if (L) is therefore mandatory in traversal procedures. If the test is forgotten, the procedure accesses NULL->data when it descends to the empty child of the first leaf, and the program crashes. A procedure called with an empty tree crashes on its very first line.
10.5.5Code trace: inorder traversal
How a recursive procedure works is understood by following the frames on the call stack. Each call adds a frame to the stack; the frame holds the L parameter of that call and the return address. When the call finishes, the frame is removed from the stack and execution continues where the caller left off. The trace below is on the four-node tree A(B(D), C): the left child of A is B and the right child is C; B has only a left child, D.
| Step | Event | Call stack | Output |
|---|---|---|---|
| 1 | L = A: inorder(B) is called for the left | A | |
| 2 | L = B: inorder(D) is called for the left | A B | |
| 3 | L = D: inorder(NULL) is called for the left | A B D | |
| 4 | L == NULL: if (L) is false, the call returns | A B D NULL | |
| 5 | L = D: its left is done, D is written | A B D | D |
| 6–7 | The NULL call for the right of D is made and returns at once; the frame of D is removed | A B D NULL | D |
| 8 | L = B: its left is done, B is written | A B | DB |
| 9–10 | The NULL call for the right of B; the frame of B is removed | A B NULL | DB |
| 11 | L = A: its left is done, A is written | A | DBA |
| 12 | L = A: inorder(C) is called for the right | A | DBA |
| 13–14 | L = C: the NULL call for the left is made and returns | A C NULL | DBA |
| 15 | L = C: C is written | A C | DBAC |
| 16–17 | The NULL call for the right of C; the frames of C and A are removed in turn | A C NULL | DBAC |
| 18 | All calls have returned | (empty) | DBAC |
NULL call for the left child of D (step 4), the writing of D (step 5), the writing of A (step 11), and the end of the traversal (step 18). The dashed nodes are frames waiting on the call stack.Three results come out of the trace. First, the first node written is D: inorder traversal descends first to the leftmost node. Second, at most four frames are on the call stack at the same time: A, B, D, and the frame opened for the empty child of D. This number is one more than the depth of the tree (3). Third, each node is entered once and left once; in the tree with four nodes, five NULL calls are made in addition to the node calls. On the same tree, preorder gives ABDC and postorder gives DBCA. The steps of the trace and the call counts are the same; only the moment of printing changes. In preorder a node is written as soon as its frame opens, and in postorder just before its frame closes.
10.5.6Cost and NULL calls
Time. The traversal procedure is called once for each node and does a constant amount of work in that call: one test, one printf, two calls. In addition there are NULL calls for the empty subtrees. The number of these calls is known exactly.
In a binary tree with n nodes, a recursive traversal procedure is called 2n + 1 times in total. Of these calls, n are made with nodes and n + 1 with NULL.
Proof. The procedure is called once for each node: the first call is made with the root and the others with the child pointers of the parent. Each node call makes two more calls; so the number of calls other than the first is 2n, which together with the first makes 2n + 1. Of the child pointers, n − 1 point to a node and n + 1 are NULL (a consequence of n0 = n2 + 1). Therefore n + 1 calls are made with NULL. ∎
The total work is proportional to 2n + 1 calls; the time is Θ(n). The shape of the tree does not change the time: a balanced tree and a skewed tree make the same number of calls. In the test with the tree A…L, 25 calls were counted for 12 nodes; 13 of them were NULL calls.
Memory. The number of frames on the call stack at the same time equals the length of the path from the root to the current node (plus at most one NULL frame). This number is at most the depth h of the tree. The memory cost is therefore O(h). In a balanced tree h = O(lg n), and in a skewed tree h = n. A balanced tree with a million nodes is traversed with about twenty frames; a skewed tree with the same number of nodes needs a million frames. In the test, in the program compiled with zig cc on Windows, a left-skewed chain of 100,000 nodes could be traversed recursively; on a chain of 300,000 nodes the call stack overflowed and the program crashed. The same chain was traversed without trouble by the iterative procedure written with a stack. These limits vary with the machine, the compiler, and the stack size.
The NULL calls can be removed by checking before the call:
/* before: n+1 calls on NULL */
preorder(L->left_child);
preorder(L->right_child);
/* after: check before calling */
if (L->left_child) preorder(L->left_child);
if (L->right_child) preorder(L->right_child);In the second form the procedure is called only for existing children, and the total number of calls drops from 2n + 1 to n. In the tree A…L, 25 calls dropped to 12. In this form, though, the if (L) at the very beginning of the procedure must remain, because the tree itself may be empty. The gain is a constant factor; the asymptotic time is still Θ(n). Because the code gets a little longer, the first, short form is preferred in most cases.
The course instructor underlines two things here. First, the claim that "recursive algorithms use a lot of memory" is often an excuse for not writing recursive code: in a balanced tree the stack depth is bounded by lg n, which is a very small number. Second, writing the algorithm is half the job; in computer science every algorithm must be analyzed. That the O(lg n) bound for memory holds only in a balanced tree, and that the general bound is O(h), is part of this analysis too.
Counting the memory of a recursive traversal as O(lg n) for every tree. This bound is correct only for balanced trees, whose depth stays of order lg n. A search tree built from sorted keys becomes skewed and its traversal needs n frames. The correct statement is "memory is O(h), lg n ≤ h ≤ n".
10.5.7The call tree
Recursive code is learned by writing, not by reading. In the instructor's analogy, watching a weightlifter a hundred times does not teach you to lift that weight. If a procedure is not understood, the tree formed by the calls is drawn on paper.
In a call tree each call is a node; the sub-calls a call makes are its children. The call tree of a traversal procedure is the traversed tree itself: there is a call for each node, and the two children of that call are the calls made for the left and right subtrees. The only difference is that the NULL calls are added as leaves. So the call tree has n internal nodes and n + 1 leaves. This is a binary tree in which every internal node has exactly two children, and it again fits the equality n0 = n2 + 1. The contents of the call stack at any moment is the path from the root to the current call in the call tree.
10.5.8Evaluating an expression tree
Finding the value of an expression tree is a postorder traversal. The value of an operator cannot be computed until the values of its two subexpressions are known. First the left subtree is computed, then the right subtree, and last the operator at the root is applied. To hold the tree, the node structure changes a little: a number is stored in the leaves and an operator in the internal nodes.
typedef struct expr *expr_pointer;
struct expr {
char op; /* '+', '-', '*', '/' */
int value; /* leaves only */
expr_pointer left, right;
};The op field holds the character '+', '-', '*', or '/'. The value field is meaningful only in leaves. left and right point to the subexpressions. Every internal node has exactly two children, because all four operators are binary; leaves have no children. If a unary operator such as unary minus (−x) were added, nodes with one child would also be needed. The evaluation procedure is:
int eval(expr_pointer t) {
if (!t->left && !t->right) /* leaf: a number */
return t->value;
int a = eval(t->left);
int b = eval(t->right);
switch (t->op) {
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
default: return a / b;
}
}The first test checks whether the node is a leaf: if both children are NULL, the node is a number and value is returned. Otherwise the value of the left subexpression is computed into a and that of the right subexpression into b. The switch returns a + b, a - b, a * b, or a / b according to the operator. The default branch handles division. The procedure must not be called with an empty tree: if t is NULL, the first line crashes. Division by zero is not checked in the division; integer division also discards the fractional part. Since the procedure visits each node once, its time is O(n), and because of the call stack its memory is O(h).
Table 10.7 traces the evaluation of the expression (8 / 4) * 3 + 5. The root of the tree is +; its left subtree is (8/4) * 3 and its right subtree is 5.
| Step | Node | Event | Returned |
|---|---|---|---|
| 1 | + | operator: left subexpression first | |
| 2 | * | operator: left subexpression first | |
| 3 | / | operator: left subexpression first | |
| 4 | 8 | leaf | 8 |
| 5–6 | / → 4 | a = 8; the right subexpression 4 is a leaf | 4 |
| 7 | / | b = 4; 8 / 4 | 2 |
| 8–9 | * → 3 | a = 2; the right subexpression 3 is a leaf | 3 |
| 10 | * | b = 3; 2 * 3 | 6 |
| 11–12 | + → 5 | a = 6; the right subexpression 5 is a leaf | 5 |
| 13 | + | b = 5; 6 + 5 | 11 |
eval finishes, the value each node returned is written beside it. The values form from the bottom up, in postorder: 8, 4, 2, 3, 6, 5, 11.The order in which the values form is 8, 4, 2, 3, 6, 5, 11. This is the postorder traversal of the tree: 8 4 / 3 * 5 +. The expression tree from the slides was built with a test program and eval was called, giving the result 11. With the same program the tree of (A + B) * (C − D) was evaluated with A = 7, B = 3, C = 9, D = 4: 10 · 5 = 50 was found.
10.6Traversal with a stack
Recursive traversal is short and readable, but it falls short in two cases. In very deep trees the call stack can overflow. In some environments (embedded systems, coding standards that forbid recursion) recursion cannot be used at all. This section writes the same traversals with a loop and an explicit stack. It then solves the nine questions in the slides by modifying the same pattern a little: iterative preorder and postorder traversal, printing leaves, and selecting nodes by number of children.
10.6.1From recursion to a loop
Every recursive algorithm can be made iterative. There are two ways. The first is to express the behavior of the algorithm directly with a loop; for example, the factorial is computed with a for loop. The second is to have the program itself do what the operating system does in recursive calls: the places to return to are put on a stack and the loop is fed from this stack. In tree traversal the second way is followed.
Consider inorder traversal. Before a node is written, the whole of its left subtree must be written. Going left from the root, every node passed is held back: first A, then B, then D. When the descent to the left ends, which of the held nodes is written? The one held last, D. After D comes B, after B comes A. So the waiting nodes are reached in the reverse of the order they were added: the last added comes out first. This is exactly the definition of a stack (LIFO). The course instructor stresses this moment with "this is a stack structure!"; it shows that the stack is not added here from outside but arises by itself from the nature of the problem.
What is put on the stack is not copies of the nodes but their addresses. A copy of a node, with its data and two pointers, takes at least 24 bytes; an address is 8 bytes. More importantly, even after it is taken off the stack the copy points to the same subtrees as the original node and is unnecessary: the address is enough to reach the node. At most as many addresses as the leftward depth of the tree are on the stack at the same time.
10.6.2Inorder traversal with a stack
Two small procedures are enough for the stack. The stack is an array of type tree_pointer and an integer holding the top index:
void push(int *top, tree_pointer p,
tree_pointer y[]) {
if (*top == MAX_SIZE - 1) {
fprintf(stderr, "Stack is full\n");
exit(EXIT_FAILURE);
}
y[++*top] = p;
}
tree_pointer pop(int *top,
tree_pointer y[]) {
return (*top == -1) ? NULL : y[(*top)--];
}If the stack is full (the top index has reached MAX_SIZE - 1), push writes a message and ends the program. Otherwise it increases the top index with ++*top and writes the address into that cell. The expression ++*top reads as ++(*top): it is not the pointer itself but the integer it points to that increases. pop returns NULL if the stack is empty; otherwise it returns the address on top and decreases the top index with (*top)--. Returning NULL from an empty stack is very convenient in this implementation, because NULL is never pushed onto the stack; a NULL return can be used to mean "the stack is empty". The traversal procedure is:
void inorder(tree_pointer L) {
tree_pointer stack[MAX_SIZE];
int top = -1;
for (;;) {
for (; L; L = L->left_child) // push lefts
push(&top, L, stack);
L = pop(&top, stack); // NULL if empty
if (!L) break;
printf("%c", L->data);
L = L->right_child;
}
}The code works line by line as follows:
tree_pointer stack[MAX_SIZE]; int top = -1;opens a local stack.top= −1 means an empty stack.- The outer loop
for (;;)is an infinite loop; its only exit is thebreakbelow. - The inner loop
for (; L; L = L->left_child)starts atL, descends to the left as far as it can, and pushes the address of every node it passes. The loop ends whenLbecomesNULL: the left child of the leftmost node has been reached. L = pop(&top, stack);takes the node on top of the stack. The left subtree of this node is either empty or completely written.if (!L) break;: if the stack is empty, the traversal is over.printf("%c", L->data);writes the node.L = L->right_child;moves to the right subtree of the node. The next iteration of the outer loop again descends to the left in this subtree. If the right subtree is empty, the inner loop does not run at all and the next node is taken from the stack.
The function also works correctly with an empty tree: if L is NULL, the inner loop does not run, pop returns NULL because the stack is empty, and the loop ends. If the stack fills up, the program ends with the message "Stack is full". MAX_SIZE should be chosen at least as large as the depth of the tree; if the depth is not known in advance, the stack is kept in a growing array.
10.6.3Code trace
The trace is on the five-node tree A(B(D, E), C): the children of A are B and C, and the children of B are D and E. Table 10.8 gives the contents of the stack and the output at each step. The values were produced with a version of the procedure that prints the stack at every push and pop.
| Step | Operation | Stack | top | L after | Output |
|---|---|---|---|---|---|
| 1 | A is pushed, descend left | A | 0 | B | |
| 2 | B is pushed, descend left | A B | 1 | D | |
| 3 | D is pushed, descend left | A B D | 2 | NULL | |
| 4 | D is popped and written; move right | A B | 1 | NULL | D |
| 5 | B is popped and written; move right | A | 0 | E | DB |
| 6 | E is pushed, descend left | A E | 1 | NULL | DB |
| 7 | E is popped and written; move right | A | 0 | NULL | DBE |
| 8 | A is popped and written; move right | (empty) | −1 | C | DBEA |
| 9 | C is pushed, descend left | C | 0 | NULL | DBEA |
| 10 | C is popped and written; move right | (empty) | −1 | NULL | DBEAC |
| 11 | pop returns NULL: break | (empty) | −1 | — | DBEAC |
top points to the top cell.The output is DBEAC and is the same as the output of recursive inorder. At most three addresses were on the stack at the same time (step 3): A, B, and D. This number is the number of nodes on the path from the root to the leftmost node. The stack has two roles. On the one hand it takes the place of the call stack of the recursive version. It also marks the moment "its left is done, its own turn is next" for a node: when a node is taken from the stack, its left subtree has been written completely.
10.6.4Cost and selective printing
Time. Each node is pushed exactly once and popped exactly once. The total number of iterations of the inner loop is n and that of the outer loop is n + 1 (the last ends with break). The total work is proportional to 2n stack operations: O(n).
Memory. At most as many addresses as the depth are on the stack at the same time: O(h). The shape of the tree changes this number markedly. In a left-skewed chain of four nodes, four addresses go onto the stack at once. In a right-skewed chain, on the other hand, each node is popped as soon as it is pushed, because no node has a left child; there is at most one address on the stack and the memory is O(1). In the test, the largest top index for the two chains came out as 3 and 0 respectively.
A nice property of the procedure is that by changing the print line it can be adapted to other jobs. If the printf line is tied to a condition, we get a procedure that writes only the selected nodes: leaves, nodes with one child, nodes with two children. When writing the condition one must be careful with the logical operators. The condition if (!(L->right_child) || !(L->left_child)) means "no right child or no left child". This condition writes leaves and nodes with one child together, that is, nodes with at most one child. For leaves alone we need "no left child and no right child": &&.
The aim of the course is to be able to write small modules skillfully; that is why small pieces of code are written again and again in different forms. The nine questions in the slides reduce to one of two patterns: recursive or stack-based traversal with a conditional printf. If "right to left" is asked for, left_child and right_child are exchanged.
10.6.5Iterative preorder traversal
The iterative version of preorder traversal is almost the same as the inorder version. The only difference is the place of printing: the node is written as it enters the stack.
void iter_preorder(tree_pointer L) {
tree_pointer stack[MAX_SIZE];
int top = -1;
for (;;) {
for (; L; L = L->left_child) {
printf("%c", L->data); // print on entry
push(&top, L, stack);
}
L = pop(&top, stack);
if (!L) break;
L = L->right_child;
}
}In the inner loop that descends to the left, each node is first written and then pushed. So the root is written before its left subtree. A node taken from the stack has already been written; it is used only to move to its right child. The result is the V-L-R order. On the tree A(B(D, E), C) the output is ABDEC.
There is a second solution to the same job. The root is pushed. At each step a node is popped and written; then first the right child and then the left child (if present) are pushed. Since the left child is pushed last, it is popped first; this makes the left subtree be traversed before the right.
if (L) push(&top, L, stack);
while ((L = pop(&top, stack))) {
printf("%c", L->data);
if (L->right_child)
push(&top, L->right_child, stack);
if (L->left_child)
push(&top, L->left_child, stack);
}This piece is the body of a function; the stack array and top = -1 are declared before it. The double parentheses in the condition while ((L = pop(&top, stack))) tell the compiler that the result of the assignment is deliberately used as the condition; if it were written with single parentheses, -Wall would give a warning. Both solutions gave ABCDGHEIJKFL on the tree A…L. In the second solution the nodes waiting on the stack are right children; each node on a path leaves at most one right child on the stack, so the memory is again O(h).
10.6.6Iterative postorder traversal
Writing postorder traversal iteratively is harder. In inorder traversal, when a node was taken from the stack its left subtree was finished and the node could be written at once. In postorder traversal, a node cannot be written before its right subtree is also finished. A node comes to the top of the stack twice: when we return from the left subtree and when we return from the right subtree. The procedure must tell these two returns apart. For this the last node written is kept in the variable last. If the node on top has a right child and the last node written is not that right child, the right subtree has not been traversed yet. First we descend to the right. Otherwise the node is written and removed from the stack.
void iter_postorder(tree_pointer L) {
tree_pointer stack[MAX_SIZE], last = NULL, t;
int top = -1;
while (L || top != -1) {
if (L) { // go left
push(&top, L, stack);
L = L->left_child;
} else {
t = stack[top]; // peek at the top
if (t->right_child && t->right_child != last)
L = t->right_child; // right first
else {
printf("%c", t->data);
last = pop(&top, stack);
}
}
}
}- The loop runs as long as there is a node to go to (
L) or a node waiting on the stack. - If
Lis not empty, the node is pushed and we descend to the left. This branch corresponds to the call "traverse the left subtree" in the recursive version. - If
Lis empty, the descent to the left is over.t = stack[top]looks at the node on top but does not take it off the stack. - If
thas a right child andlastis not that child, the right subtree has not been traversed yet;Lis set to the right child. - Otherwise (there is no right child or it was just written), both subtrees of
tare finished.tis written, popped from the stack, and recorded inlast.
Why last is compared only with the right child is explained as follows. In postorder, the node written immediately before a node is the root of its right subtree if it has one, that is, the right child. If the right subtree is empty, it is the left child, or the node is a leaf. So the question "is the last written node the right child?" tells with certainty whether the right subtree is finished.
| Step | Event | Stack | last | Output |
|---|---|---|---|---|
| 1 | L = A is pushed, L = B | A | NULL | |
| 2 | L = B is pushed, L = D | A B | NULL | |
| 3 | L = D is pushed, L = NULL | A B D | NULL | |
| 4 | Top D: no right child → D is written, popped | A B | D | D |
| 5 | Top B: no right child → B is written, popped | A | B | DB |
| 6 | Top A: it has right child C and last ≠ C → L = C | A | B | DB |
| 7 | L = C is pushed, L = NULL | A C | B | DB |
| 8 | Top C: no right child → C is written, popped | A | C | DBC |
| 9 | Top A: right child C = last → A is written, popped | (empty) | A | DBCA |
| 10 | L is NULL and the stack is empty: the loop ends | (empty) | A | DBCA |
A comes to the top twice: at step 6 and at step 9. The first time last = B and the right subtree has not been traversed yet; the second time last = C and A is written. The time is again O(n): each node is pushed once, popped once, and looked at at most twice while on top. The memory is O(h). The procedure gave GHDJKIECBLFA on the tree A…L and DEBCA on the tree A(B(D, E), C); both are the same as the recursive version.
Another solution uses two stacks: the V-R-L order is produced with the first stack and pushed onto the second; when the second stack is emptied, L-R-V comes out. This solution is easier to understand but needs O(n) extra memory.
Popping the node on top instead of looking at it: t = pop(&top, stack);. If the right subtree has not been traversed yet, t must be pushed back; if it is not, t is never written after the right subtree has been traversed. In postorder traversal a node is taken from the stack only at the moment it is to be written; until then it waits on top.
10.6.7Printing the leaf nodes
To write the leaf nodes from left to right, any traversal can be used, because the relative order of the leaves is the same in all three standard traversals. In inorder traversal the printf is tied to a condition:
void print_leaves(tree_pointer L) {
if (L) {
print_leaves(L->left_child);
if (!L->left_child && !L->right_child)
printf("%c", L->data);
print_leaves(L->right_child);
}
}The condition is that the node has neither child. On the tree A…L the output is GHJKL. To write from right to left, only the order of the two recursive calls is changed: first right, then left.
void print_leaves_right(tree_pointer L) { /* Q4 */
if (L) {
print_leaves_right(L->right_child);
if (!L->left_child && !L->right_child)
printf("%c", L->data);
print_leaves_right(L->left_child);
}
}This procedure gives LKJHG on the same tree; it is the reverse of the left-to-right output. The iterative version follows the same path. In the inorder procedure with a stack, the printf line is tied to this condition:
if (!L->left_child && !L->right_child)
printf("%c", L->data);To write from right to left iteratively, left_child and right_child are exchanged everywhere in the stack code: rights are pushed onto the stack, and after a node is popped we go left.
void iter_print_leaves_right(tree_pointer L) { /* Q6 */
tree_pointer stack[MAX_SIZE];
int top = -1;
for (;;) {
for (; L; L = L->right_child) // push rights
push(&top, L, stack);
L = pop(&top, stack);
if (!L) break;
if (!L->left_child && !L->right_child)
printf("%c", L->data);
L = L->left_child;
}
}This code is a reverse inorder traversal (R-V-L). The leaves come out in reverse order. All four procedures were run on the same tree in the test program: the left-to-right versions gave GHJKL and the right-to-left versions gave LKJHG. All run in O(n) time; the call stack of the recursive versions and the explicit stack of the iterative versions need O(h) memory.
10.6.8Selecting by number of children
The last three questions select nodes by the state of their children. The recursive procedure that writes the nodes that have only a left child is:
void print_left_only(tree_pointer L) { /* Q7 */
if (!L) return;
if (L->left_child && !L->right_child)
printf("%c", L->data);
print_left_only(L->left_child);
print_left_only(L->right_child);
}This procedure is in preorder form: it tests the condition, writes if necessary, and then descends into the two subtrees. The early return if (!L) return; at the beginning of the procedure takes the place of the block if (L) { … }. The condition L->left_child && !L->right_child reads "has a left child and has no right child"; !L->right_child means "the right child pointer is NULL". The other two questions change only the condition. For nodes that have only a right child, the condition is !L->left_child && L->right_child. For nodes with two children, the condition is L->left_child && L->right_child:
void print_two_children(tree_pointer L) { /* Q9 */
if (!L) return;
if (L->left_child && L->right_child)
printf("%c", L->data);
print_two_children(L->left_child);
print_two_children(L->right_child);
}In the tree A…L, the only node with just a left child is F; the nodes with just a right child are B and E; the nodes with two children are, in preorder, A, C, D, and I. The consistency of the numbers can be checked with Theorem 10.2: the tree has 5 leaves, 3 nodes with one child, and 4 nodes with two children; 5 = 4 + 1 and 5 + 3 + 4 = 12. All these procedures are examples of the pattern "traverse the tree and write if the condition holds". The kind of traversal determines only the order of the output; the set of selected nodes is independent of the traversal.
Writing || instead of && in the leaf condition: if (!L->left_child || !L->right_child). This condition writes all nodes that are missing at least one child. In the tree A…L, B, E, and F are written in addition to the leaves, and the output becomes BGHEJKLF. The compiler does not notice this mistake; it comes to light only when the output is compared by hand with the expected output on a small test tree.
10.7Level-order traversal
Preorder, inorder, and postorder traversals go into the depths of the tree: once they enter a branch, they do not move to the next branch before finishing it. In some jobs, however, the nodes must be visited by their distance from the root: first the root, then all the nodes at level 2 from left to right, then level 3, and so on. This is called level-order traversal. This section solves the same question with two methods and shows why the second method matches a queue naturally.
10.7.1With level lists
The first method rests on noticing that the order of traversal does not matter. The tree is traversed with any traversal and each node is appended to the end of the list of its own level. When the traversal is finished, the lists are written in order starting from level 1. It is enough to give the traversal procedure the level of the node as a parameter: the root is called with 1, and each child with one more than the level of its parent. For the lists, an array of linked lists is kept; cell i of the array points to the head of the list of level i.
Since appending to the lists is always done at the end, the order of the nodes in each list is the order in which the traversal found them. To keep left-to-right order, a traversal that visits the left before the right (preorder, inorder, or postorder) must be chosen. Of two nodes on the same level, the one on the left is found first in all three traversals. In the tree of Figure 10.17 the lists are A; B, C; D, E, F, G; H, and written one after another they give ABCDEFGH.
Cost. Each node is handled three times: it is found in the traversal, appended to a list, and written from the list. Appending to the end of a list is O(1) with a tail pointer; the total time is 3n = O(n). The memory is the n nodes of the lists, the h cells of the array of level heads, and the O(h) call stack of the traversal: O(n + h). Since h is at most n, this is O(n).
10.7.2With a queue
The second method produces the same order without building extra lists. In level-by-level writing, the children of a node must be written after all the other nodes of the same level. When the root is written, its children B and C enter the line. When B is written, the children of B, D and E, also enter the line, but behind C, because C must be written before D and E. The one that enters the line first leaves first: this is the definition of a queue (FIFO). In depth-wise traversal, using a stack came from the nature of the problem; in level-order traversal, using a queue is just as inevitable.
The algorithm is as follows. The root is put into the queue. Until the queue is empty, at each step a node is taken from the front of the queue, written, and its children (first left, then right, if present) are appended to the back of the queue. Since the tree may be empty, the procedure begins with the test if (!L) return;. What is put into the queue is the addresses of the nodes, not copies. The queue is implemented as a circular array:
void enqueue(int front, int *rear,
tree_pointer p, tree_pointer q[]) {
*rear = (*rear + 1) % MAX_SIZE;
if (*rear == front) { /* full */
fprintf(stderr, "Queue is full\n");
exit(EXIT_FAILURE);
}
q[*rear] = p;
}
tree_pointer dequeue(int *front, int rear,
tree_pointer q[]) {
if (*front == rear) return NULL; /* empty */
*front = (*front + 1) % MAX_SIZE;
return q[*front];
}Two indices are kept in the circular queue. rear points to the cell of the last element added, and front to the cell just before the first element. If the two are equal, the queue is empty. enqueue advances rear by one; if the end of the array has been reached, it wraps to the beginning with % MAX_SIZE. If the advanced rear turns out equal to front, the queue is full: if one more element were added, an empty queue could not be told from a full one. So in an array of MAX_SIZE cells at most MAX_SIZE - 1 elements are held. dequeue returns NULL if the queue is empty; otherwise it advances front and returns the address in that cell. The index each procedure will change is passed to it by address: enqueue changes rear and dequeue changes front. The level-order traversal procedure is:
void level_order(tree_pointer L) {
tree_pointer queue[MAX_SIZE];
int front = 0, rear = 0;
if (!L) return; // tree may be empty
enqueue(front, &rear, L, queue);
while ((L = dequeue(&front, rear, queue))) {
printf("%c", L->data);
if (L->left_child)
enqueue(front, &rear, L->left_child, queue);
if (L->right_child)
enqueue(front, &rear, L->right_child, queue);
}
}The line while ((L = dequeue(&front, rear, queue))) both takes a node from the queue and tests whether the queue has become empty: when dequeue returns NULL, the loop ends. The loop body writes the node taken and appends its existing children at the back. NULL children are never put into the queue; so a NULL coming out of the queue means only "the queue is empty".
10.7.3Code trace
Table 10.10 traces the state of the queue on the tree A…H. Cell 0 of the queue array is never used, because the first insertion advances rear from 0 to 1. The values were produced with a version of the procedure that prints front and rear at every removal.
| Step | Removed (front) | Added | rear | Left in the queue | Output |
|---|---|---|---|---|---|
| 1 | A (1) | B, C | 3 | B C | A |
| 2 | B (2) | D, E | 5 | C D E | AB |
| 3 | C (3) | F, G | 7 | D E F G | ABC |
| 4 | D (4) | H | 8 | E F G H | ABCD |
| 5 | E (5) | — | 8 | F G H | ABCDE |
| 6 | F (6) | — | 8 | G H | ABCDEF |
| 7 | G (7) | — | 8 | H | ABCDEFG |
| 8 | H (8) | — | 8 | (empty) | ABCDEFGH |
| 9 | front == rear: NULL | — | 8 | (empty) | ABCDEFGH |
front points to the cell before the first element and rear to the last element.If we look at the contents of the queue, at any moment the queue holds nodes of at most two consecutive levels: the not-yet-written nodes of one level and the children of those ahead of them. After step 4 the queue holds E, F, G from level 3 and H from level 4. The same procedure gave ABFCLDEGHIJK on the tree A…L. When called with an empty tree it returned without writing anything.
10.7.4Cost: stack versus queue
Time. Each node enters the queue once and leaves once: 2n = O(n).
Memory. The queue holds at most as many nodes as the width (w) of one level, plus a few nodes from the next level. So the extra memory is O(w). In a complete tree the last level has about n/2 nodes and the memory is O(n). In a skewed tree there is a single node at each level and the queue never holds more than one node: O(1). In depth-wise traversals the situation is the reverse: in a balanced tree the stack needs O(lg n) and in a skewed tree O(n) memory. Table 10.11 compares the two families of traversal.
| Traversal | Auxiliary structure | Extra memory | Balanced tree | Skewed tree |
|---|---|---|---|---|
| Preorder / inorder / postorder | stack (LIFO) | O(h) | O(lg n) | O(n) |
| Level-order | queue (FIFO) | O(w) ≤ O(n) | O(n) | O(1) |
The contrast in the table is important: the O(lg n) memory bound does not hold for level-order traversal with a queue but for depth-wise traversals with a stack in a balanced tree. The same ideas have counterparts in graphs. Level-order traversal with a queue is called breadth-first search (BFS) in graphs. When a stack is used instead of a queue, the algorithm turns into depth-first search (DFS). Since a node in a graph can be reached by more than one path, visited marks are also kept there.
10.8Other tree procedures
The traversal pattern applies not only to printing but to almost any job on a tree. The four procedures in this section use the same skeleton: handle the empty tree, do a piece of work at the root, call yourself for the two subtrees. The difference is in what the work at the root is and in how the results of the recursive calls are combined.
10.8.1Copying a tree
A copy of a tree is a tree with the same shape and the same data but built entirely from new nodes. The copy must not share even a single node with the original tree; otherwise a change made in the copy would also corrupt the original. The procedure is defined recursively as follows: the copy of the empty tree is the empty tree; the copy of a non-empty tree is obtained by attaching the copies of the two subtrees under a new root.
tree_pointer copy(tree_pointer L) {
if (!L) return NULL;
tree_pointer T = malloc(sizeof *T);
if (!T) { perror("malloc"); exit(1); }
T->left_child = copy(L->left_child);
T->right_child = copy(L->right_child);
T->data = L->data;
return T;
}if (!L) return NULL;returns the copy of the empty tree. This also comes into play in the calls made for the children of leaves.tree_pointer T = malloc(sizeof *T);reserves space for the new root. If the allocation fails,perrorwrites an error message and the program ends. Heremallocand a check are used directly instead ofget_node; both forms are correct.T->left_child = copy(L->left_child);builds the copy of the left subtree and writes it into the left link of the new root.T->right_child = copy(L->right_child);does the same for the right subtree.T->data = L->data;copies the data andreturn T;gives the address of the new root to the caller.
The data is written after the two children are copied; the procedure traverses the tree in postorder form. The copy is built from the bottom up: first the leaves, then their parents. The course instructor notes that this procedure works bottom-up and could also be written top-down. By changing the places of the lines one easily moves to the preorder or inorder form: for example, if the line T->data = L->data; is moved right after the malloc, the data is copied before the children. The result does not change. The recommended way to work is, before writing the code, to draw the calls with a small tree on paper as on the board and to see how the procedure is resolved recursively.
Copying the tree A(B, C) finishes in sixteen steps: three malloc calls for three nodes, four NULL calls, three data copies, and writing the returned addresses into the links. In the test program the preorder and inorder outputs of the copy were the same as those of the original tree (ABC and BAC); it was also checked that the node addresses of the copy differ from those in the original tree. The copy of the tree A…L was compared with the original using equal and found equal. Cost: time O(n), call stack O(h); the copy itself takes up n nodes of space. The copy is now an independent tree and must be freed separately with tree_free when its job is done.
10.8.2Equivalence
Two binary trees are equal if they have the same shape and the data at corresponding nodes are the same. If only the shape matters, the trees are called isomorphic. The recursive definition is as follows. If both trees are empty, they are equal. If one is empty and the other is not, they are not equal. If both are non-empty, the data at the roots must be equal, the left subtrees must be equal, and the right subtrees must be equal.
int equal(tree_pointer L, tree_pointer T) {
return (!L && !T) ||
(L && T && L->data == T->data
&& equal(L->left_child, T->left_child)
&& equal(L->right_child, T->right_child));
}The function consists of a single return expression. The left side of || catches the case where both trees are empty and gives 1. The right side is five conditions joined with &&: L is non-empty, T is non-empty, the data are equal, the left subtrees are equal, the right subtrees are equal. The operators && and || of C short-circuit: they do not evaluate the right side once the result is known. This gives two benefits. First, if L or T is NULL, L->data is never accessed; the test L && T acts as a guard. Second, the recursion stops at the first difference and the remaining nodes are not looked at. If only structural similarity is wanted, the condition L->data == T->data is removed.
| Step | Call | Event | Result |
|---|---|---|---|
| 1 | (A, A) | both non-empty, data equal; move to the left subtrees | |
| 2 | (B, B) | both non-empty, data equal; move to the left subtrees | |
| 3 | (NULL, NULL) | !L && !T is true; the right of || is not evaluated | 1 |
| 4 | (B, B) | left subtrees equal; move to the right subtrees | |
| 5 | (NULL, NULL) | both empty | 1 |
| 6 | (B, B) | all conditions true | 1 |
| 7 | (A, A) | left subtrees equal; move to the right subtrees | |
| 8 | (C, D) | data differ; && short-circuits, the subtrees are not looked at | 0 |
| 9 | (A, A) | the right side returned 0 | 0 |
In the trace five calls are made in total: (A, A), (B, B), two times (NULL, NULL), and (C, D). The children of C and D are never looked at. Cost. In the worst case, when the trees are equal, all the nodes of the two trees are compared. If the trees differ, the procedure stops at the first difference; no more comparisons are made than the number of nodes of the smaller tree. The time is O(min(n1, n2)) and the call stack O(h).
The course instructor draws attention to a contrast here: checking whether binary trees are isomorphic is this easy, whereas finding the isomorphism of two general graphs is a very hard problem. The reason for the difference is the ordered structure of the binary tree. Since the left and right child of each node are known, which node will match which is determined automatically. In a graph the nodes have no order, and the number of possible matchings grows as large as the factorial of the number of nodes.
10.8.3Writing with early returns
The same procedure can be written, instead of as one long expression, in a form that tests each condition on a separate line and returns at once when the result is known. This way of writing is called guard style (early return):
int equal2(tree_pointer L, tree_pointer T) {
if (L == NULL || T == NULL)
return L == T; /* both NULL? */
if (L->data != T->data)
return 0;
if (!equal2(L->left_child, T->left_child))
return 0;
return equal2(L->right_child, T->right_child);
}The first test runs when at least one of the two trees is empty. In this case the expression return L == T; tells whether both are empty: while one is NULL, L == T is true only if the other is NULL too. The second test compares the data. The third compares the left subtrees and returns 0 at once if they are not equal. The last line leaves the result directly to the comparison of the right subtrees. The behavior is the same as equal; in the test the two procedures gave the same results on all pairs of trees.
In both styles the return value of every recursive call is used. This is a point often skipped when writing recursive functions. If the line equal2(L->left_child, T->left_child); were written without passing its result anywhere, the computed value would be lost and the function would turn into a test that looks only at the data of the roots. In the instructor's words, a student who says "mine works nicely but it doesn't return" has not yet learned to write recursive algorithms: every call must return a value and the caller must use that value.
Not using the result of a recursive call, or trying to do work after return. A procedure of the form if (L->data != T->data) return 0; equal2(L->left_child, T->left_child); return 1; compiles and gives the right result when the two trees really are equal. But it also returns 1 for different subtrees, because the result of the recursive call is discarded. The lines after the return line never run.
10.8.4Swapping the left and right children
The mirror image of a tree is obtained by exchanging the left and right subtrees of every node. The procedure swaps not the data but only the pointers:
#define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t))
void swap_children(tree_pointer L) {
tree_pointer p;
if (L) {
SWAP(L->left_child, L->right_child, p);
swap_children(L->left_child);
swap_children(L->right_child);
}
}The SWAP macro takes three arguments: the two values to be swapped and a temporary variable. ((t) = (x), (x) = (y), (y) = (t)) performs three assignments in a single expression with the comma operator: the value of x is saved in t, y is written into x, and the saved value is written into y. Using the macro parameters in parentheses makes it expand correctly even with complex arguments such as L->left_child. The temporary variable in the procedure is tree_pointer p. The root is swapped, and then the procedure is repeated for the two subtrees. Since the swap is done before the calls, the procedure is in preorder form.
After the swap, L->left_child is the old right subtree. So on the tree A(B(D), C) the procedure descends first to C and then to B. Table 10.13 gives the steps.
| Step | Call | Event |
|---|---|---|
| 1 | A | left (B) and right (C) are swapped; the left of A is now C |
| 2 | C | left (NULL) and right (NULL) are swapped |
| 3–4 | NULL, NULL | the calls for the two empty children of C return at once |
| 5 | B | left (D) and right (NULL) are swapped; the right of B is now D |
| 6 | NULL | the new left child of B is empty |
| 7 | D | left (NULL) and right (NULL) are swapped |
| 8–9 | NULL, NULL | the calls for the two empty children of D return |
| 10 | — | done: the tree has become A(C, B(—, D)) |
As a result the inorder sequence turns from DBAC into CABD. The inorder sequence of a mirror tree is always the reverse of that of the original, because the mirror turns the order L-V-R into R-V-L at every node. The procedure visits each node once and makes a constant number of assignments at each node: time O(n), memory O(h). No node is allocated or freed; the data stay in place and only the pointers change places. If the procedure is applied twice, the tree returns to its original state.
10.8.5The place of the swap
The SWAP line can be placed before, between, or after the two recursive calls. Before and after, the result is the same; in between, the result goes wrong. To see this, a right-skewed chain in which all the subtrees on the right are single-armed is used: B on the right of A, C on the right of B, D on the right of C. Figure 10.21 shows the cases.
- Swap first (preorder): At A, left and right are exchanged; B is now on the left of A and the procedure descends into B. The swap also happens at B and C moves to the left. The result is a left-skewed chain: the exact mirror.
- Swap last (postorder): First the two subtrees are mirrored internally, then the swap is made at the root. Since each subtree changes places after it has been mirrored, the result is again the exact mirror.
- Swap in between (inorder): At A, first the left subtree is processed; since the left is empty, nothing happens. Then the swap is made and B moves to the left. Next the "right" subtree is processed; but the right is now empty. The subtree of B is never entered. In the end only the root has been swapped.
The three versions were run in the test program. With the swap first and last, the inorder sequence came out DCBA and the two trees were found equal with equal. With the swap in between, the inorder sequence came out BCDA. The general lesson is this: every call of the procedure reads the subtree it will process from the pointers as they are at the moment of the call. If the swap changes these pointers between the calls, the second call goes to the wrong subtree.
10.9Rebuilding a tree from traversals
A single traversal output does not determine a tree. For example, there are two trees with inorder output AB: A the root and B the right child, or B the root and A the left child. When two traversals are given together, in most cases the tree is found uniquely. This is a frequently asked exam question. In the question in the slides the inorder sequence is C M D A K N B F E G and the postorder sequence is D A N F E B K M G C. The binary tree that gives these sequences is to be drawn.
The method rests on two observations. In the postorder sequence, the root of every subtree is the last-written node of that subtree. In the inorder sequence, the letters to the left of a node form its left subtree and the letters to the right form its right subtree. The postorder sequence is read from the end to the beginning. Each letter is the root of a subtree; the inorder sequence separates the left and right of this letter. In reading from the end, the roots of the right subtree come first and then those of the left subtree, because in postorder the right subtree is immediately before the root.
| Step | Read from postorder | Position in the inorder sequence | Placement |
|---|---|---|---|
| 1 | C (last) | no letters on its left | C is the root; the left subtree is empty, the right subtree is MDAKNBFEG |
| 2 | G | no letters on its right | G is the right child of C; the right of G is empty, the left is MDAKNBFE |
| 3 | M | no letters on its left in this subtree | M is the left child of G; the left of M is empty |
| 4 | K | D, A on its left; N, B, F, E on its right | K is the right child of M |
| 5 | B | the root of the right subtree of K | B is the right child of K; N on its left, F, E on its right |
| 6 | E | the root of the right subtree of B; F on its left | E is the right child of B |
| 7 | F | on the left of E | F is the left child of E |
| 8 | N | on the left of B | N is the left child of B |
| 9 | A | the root of the left subtree of K, D, A | A is the left child of K |
| 10 | D | on the left of A | D is the left child of A; the tree is complete |
The order in the table is the postorder string read from the end to the beginning: C, G, M, K, B, E, F, N, A, D. When the slides draw the same tree step by step, they place the left subtree of K (D and A) before its right subtree; both orders give the same tree. Figure 10.22 shows an intermediate moment and the result.
The resulting tree was checked with the test program: the inorder traversal of the built tree gave CMDAKNBFEG and the postorder traversal gave DANFEBKMGC. The method turns directly into a recursive C function:
/* inord: inorder, postord: postorder string; both n letters */
tree_pointer rebuild(const char *inord, const char *postord, int n) {
if (n == 0) return NULL;
tree_pointer T = get_node();
T->data = postord[n - 1]; /* postorder: root is last */
int i = 0;
while (inord[i] != T->data) i++; /* find the root in inorder */
T->left_child = rebuild(inord, postord, i);
T->right_child = rebuild(inord + i + 1, postord + i, n - i - 1);
return T;
}inord is the inorder string and postord the postorder string; both hold the n letters of the same subtree. The root is the last letter of postord. The position i of the root is found in the inorder string: the i letters to its left are the left subtree and the n - i - 1 letters to its right are the right subtree. In the postorder string, too, the left subtree takes the first i letters and the right subtree the following n - i - 1 letters. The left subtree is built with (inord, postord, i). The right subtree is built with (inord + i + 1, postord + i, n - i - 1). Pointer arithmetic avoids copying substrings: inord + i + 1 is the part of the string starting from character i + 1. The function assumes that the letters are all distinct and that the two strings belong to the same tree. For each node a linear search is made in the inorder string; in a skewed tree the total time is O(n2) and in a balanced tree O(n lg n).
Preorder and inorder sequences also determine the tree uniquely; the only difference is that the root is the first letter of the preorder sequence. Preorder and postorder sequences, on the other hand, generally do not determine it. Consider two trees in which A is the root and B the only child: in one B is on the left, in the other on the right. Both have preorder AB and postorder BA. These two traversals find the root and the child, but do not say on which side the single child is. The inorder sequence carries exactly this information: the left subtree is written before the root and the right subtree after it.
10.10Complexity summary
Table 10.15 collects the time and extra-memory costs of all the procedures in these notes. n is the number of nodes and h the depth; lg n ≤ h ≤ n (balanced ↔ skewed). In this course depth is measured by the number of levels.
| Operation | Time | Extra memory | Description |
|---|---|---|---|
| Parent / child (array representation) | O(1) | 2k − 1 cells | no loss in a complete tree |
| Recursive preorder / inorder / postorder | O(n) | O(h) | 2n + 1 calls, n + 1 of them NULL |
| Preorder / inorder / postorder with a stack | O(n) | O(h) | addresses are pushed on the stack |
| Level-order (queue) | O(n) | O(w) ≤ O(n) | w: the widest level |
| Printing leaves, selecting by number of children | O(n) | O(h) | traversal + condition |
eval (expression tree) | O(n) | O(h) | postorder |
copy | O(n) | O(h) + n nodes | postorder |
tree_free | O(n) | O(h) | postorder is mandatory |
equal, equal2 | O(min(n1, n2)) | O(h) | stops at the first difference |
swap_children | O(n) | O(h) | pointers only |
rebuild | O(n2) worst case | O(h) + n nodes | searching for the root is linear |
Every procedure that touches all the nodes needs Ω(n) time; all the procedures here reach this lower bound. In memory the deciding factor is the shape of the tree: a balanced tree is traversed with a few dozen frames, a skewed tree with n frames.
10.11Common mistakes
- Accessing
L->datawithout aNULLcheck. The tree pointer can beNULL: the tree may be empty, or the recursion may have descended to the empty child of a leaf. The first question of every tree procedure should be "is the tree empty?". - Starting at 0 in the array representation and using the 1-based formulas. The formulas 2i and 2i + 1 are correct when the root is in cell 1. If the root is in cell 0, the formulas are 2i + 1, 2i + 2, and ⌊(i − 1)/2⌋.
- Putting a copy of a node on the stack or queue. The address is enough to reach the node. A copy both takes more space and means an unnecessary memory allocation or structure copy.
- Not using the return value of a recursive call, or trying to do work after
return. The result of every recursive call that returns a value must either be returned or stored in a variable. - Writing
||instead of&&in the leaf condition. "Has no children" means that neither child exists. With||, nodes with one child are written too. - Mixing up degree and depth, or the definitions of level 1 and depth 0. Degree measures width, depth measures length. The level of the root is 1 in this course; in other sources it may be 0, and the formulas shift by one accordingly.
- Freeing the root first when deleting a tree. Reading
L->left_childafterfree(L)is undefined behavior. Deletion must be done in postorder.
10.12Exercises and solutions
The six questions on the exercise slide of the slides are given below with their solutions. The solutions that contain code were compiled and run with small test programs; the solutions that ask for a tree drawing were checked with a Python script.
10.12.1The leaf-count equality
Question. Prove the equality n0 = n2 + 1.
Solution. If the nodes are counted by degree, n = n0 + n1 + n2. An edge enters every node other than the root from above; the number of edges is n − 1. If the same edges are counted by the nodes they leave, we get n − 1 = n1 + 2n2. Subtracting the two equations side by side leaves 1 = n0 − n2. The details of the proof are given in Theorem 10.2. In the tree A…L, n0 = 5, n1 = 3, and n2 = 4 were counted; the equality holds.
10.12.2Three traversals of an expression tree
Question. Draw the tree of the expression (A + B) * (C − D) and write the three traversals.
Solution. The last operator applied is *; it is the root. The root of the left subtree is +, with children A and B. The root of the right subtree is -, with children C and D. Preorder gives * + A B - C D. Inorder gives A + B * C - D and postorder gives A B + C D - *. In the inorder output the parentheses are lost; to read the expression correctly, each subtree must be put in parentheses. The prefix and postfix outputs are unambiguous even without parentheses.
10.12.3Number of nodes
Question. Write the procedure int count_nodes(tree_pointer L) that returns the number of nodes of a tree.
int count_nodes(tree_pointer L) { /* node count */
return L ? 1 + count_nodes(L->left_child) + count_nodes(L->right_child) : 0;
}Solution. The empty tree has no nodes: 0. In a non-empty tree, 1 for the root is added to the two recursive calls for the nodes of the two subtrees. The conditional operator (? :) combines the two cases in a single return expression. The procedure is in postorder form: the value for the root is computed after the values for the subtrees are known. The time is O(n) and the memory O(h). In the test program it returned 12 for the tree A…L, 4 for A(B(D), C), and 0 for the empty tree. With the same pattern, the number of leaves (1 if L is a leaf, otherwise the sum for the two subtrees) and the depth are written too.
10.12.4A tree from the preorder and inorder sequences
Question. Draw the tree whose preorder is A B D E C F and whose inorder is D B E A F C.
Solution. The first letter of the preorder sequence is the root: A. In the inorder sequence, D, B, E are on the left of A and F, C on the right. The preorder of the left subtree is B, D, E; its root is B. In the inorder sequence, D is on the left of B and E on the right: B(D, E). The preorder of the right subtree is C, F; its root is C. In the inorder sequence, F is on the left of C: C(F, —). The tree is A(B(D, E), C(F, —)). This method is the same as the method of Table 10.14; the only difference is that the root is read from the beginning.
10.12.5Writing the levels from right to left
Question. Write the queue-based procedure that writes the levels of a tree in order, but each level from right to left.
void level_order_right(tree_pointer L) { /* levels right to left */
tree_pointer queue[MAX_SIZE];
int front = 0, rear = 0;
if (!L) return;
enqueue(front, &rear, L, queue);
while ((L = dequeue(&front, rear, queue))) {
printf("%c", L->data);
if (L->right_child)
enqueue(front, &rear, L->right_child, queue);
if (L->left_child)
enqueue(front, &rear, L->left_child, queue);
}
}Solution. Its only difference from level_order is the order in which the children are added to the queue: first the right child, then the left. The nodes of the same level enter the queue from right to left and leave in the same order. On the tree A…H the output was ACBGFEDH: level 1 A, level 2 C B, level 3 G F E D, level 4 H. The cost is the same as that of level_order.
10.12.6Are two trees mirror images of each other?
Question. Write the procedure that checks whether two trees are mirror images of each other.
int is_mirror(tree_pointer L, tree_pointer T) {
return (!L && !T) ||
(L && T && L->data == T->data
&& is_mirror(L->left_child, T->right_child)
&& is_mirror(L->right_child, T->left_child));
}Solution. Its only difference from equal is the crossed comparison: the left of L is compared with the right of T, and the right of L with the left of T. The tree A(B(D), C) was mirrored with swap_children and then compared with the original tree, and it returned 1. Comparing a tree with itself gave 0, because the tree is not symmetric. The time is O(min(n1, n2)) and the memory O(h).
10.13Summary
- A tree is a hierarchical structure that starts from a root and splits into disjoint subtrees. Every node other than the root has a single parent; so a tree has no cycles and has n − 1 edges in n nodes.
- Basic terms: parent, child, sibling, ancestor, descendant, degree, leaf, internal node, level, and depth. In this course the root is at level 1 and the depth is the largest level; sources such as CLRS count the root as 0.
- A binary tree has at most 2i−1 nodes at level i and at most 2k − 1 nodes in a tree of depth k. ⌈lg(n + 1)⌉ ≤ k ≤ n; the lower bound is reached by the complete tree and the upper bound by the skewed tree.
- n0 = n2 + 1. In the linked representation, n + 1 of the 2n pointers are
NULL. - A complete and fixed tree is kept in an array (1-based, ⌊i/2⌋, 2i, 2i + 1), and a tree whose shape changes with
tree_pointerlinks. A skewed tree needs 2k − 1 cells in an array. - A general tree is converted to a binary tree with the left-child right-sibling representation; the preorder is preserved, and the inorder of the binary tree equals the postorder of the general tree.
- Preorder, inorder, and postorder traversals are the same recursive skeleton; they make 2n + 1 calls and need O(n) time and O(h) memory. An expression tree is evaluated with a postorder traversal.
- Traversals are written iteratively with an explicit stack; node addresses are put on the stack. In the postorder version the last written node is kept.
- Level-order traversal needs a queue; its memory is proportional to the widest level.
- Copying, isomorphism, mirroring, counting, and deleting are examples of the "traverse and process" pattern. Deletion and copying are done in postorder.
- The inorder sequence together with the postorder or preorder sequence determines the tree uniquely; preorder and postorder together do not.
10.14Key terms
- tree
- root
- subtree
- graph
- parent
- child
- sibling
- ancestor
- descendant
- degree
- leaf
- internal node
- level
- depth
- height
- binary tree
- skewed tree
- perfect binary tree
- complete binary tree
- threaded binary tree
- traversal
- preorder
- inorder
- postorder
- level-order
- expression tree
- call stack
- circular queue
- isomorphic
- breadth-first search
- depth-first search
- balanced tree
10.15Test Yourself
In the general tree A–M (the children of A are B, C, D; the children of B are E, F; the children of E are K, L; the child of C is G; the children of D are H, I, J; the child of H is M), what are the level of H, the degree of D, the ancestors of E, and the descendants of B?
Answer
H is at level 3. The degree of D is 3 (H, I, J). The ancestors of E are A and B. The descendants of B are E, F, K, and L.
What is the maximum number of nodes in a binary tree of depth 5? What is the maximum number of nodes at level 4 of this tree?
Answer
At most 25 − 1 = 31 nodes. At level 4, at most 23 = 8 nodes.
A complete binary tree with 20 nodes is kept in a 1-based array. What is the depth of the tree? What are the parent and the children of node 14? Does node 10 have children?
Answer
The depth is ⌈lg 21⌉ = 5. The parent of 14 is ⌊14/2⌋ = 7; its children would be 28 and 29, but both exceed 20, so they do not exist (14 is a leaf). Node 10 has a left child, 20; its right child, 21, does not exist.
A binary tree has 7 nodes with two children and 3 nodes with one child. How many leaves are there? How many
NULLpointers are there in the linked representation?Answer
There are n0 = n2 + 1 = 8 leaves. The total number of nodes is 8 + 3 + 7 = 18 and the number of
NULLpointers is n + 1 = 19.In a tree, the children of A are B and C and the children of B are D and E; C has only a right child, F. What are the outputs of the four traversals (preorder, inorder, postorder, level-order)?
Answer
Preorder ABDECF, inorder DBEACF, postorder DEBFCA, level-order ABCDEF.
What is the tree of the expression whose postfix notation is
A B + C *? What is its prefix notation?Answer
The root is
*; its left subtree is+(A, B) and its right child is C. The expression is (A + B) * C. The prefix notation is* + A B C.Inorder traversal with a stack is applied to a left-skewed chain of 1000 nodes. At most how many addresses are on the stack at the same time? What if the chain were right-skewed?
Answer
In the left-skewed chain, starting from the root, all the nodes are pushed onto the stack while descending to the left: 1000 addresses (
MAX_SIZEmust be at least this large). In the right-skewed chain no node has a left child, so each node is popped as soon as it is pushed: at most 1 address.equalis called with the trees A(B, C) and A(B, C(D, —)). What is the result and how many calls are made in total?Answer
The result is 0. The calls: (A, A), (B, B), two (NULL, NULL) for the two empty children of B, (C, C), and (NULL, D) for the left children of the C's. In the last call both conditions come out false and 0 is returned; since
&&short-circuits, the right children of the C's are not looked at. Six calls in total.Which tree has preorder ABDGCEF and inorder DGBAECF?
Answer
The root is A. The left subtree is {D, G, B}: its root is B, with D, G on the left of B; D is the root and G is its right child. The right subtree is {E, C, F}: its root is C, left child E, right child F. The tree is A(B(D(—, G), —), C(E, F)).
swap_childrenis applied to the tree A(B(D, E), C). What is the inorder sequence of the new tree? What happens if the procedure is applied a second time?Answer
The original inorder sequence is DBEAC; that of the mirror tree is its reverse: CAEBD. The second application undoes the swap at every node and the tree returns to its original state.
10.16Further reading
- E. Horowitz, S. Sahni, and S. Anderson-Freed, Fundamentals of Data Structures in C (2nd ed.), Chapter 5: the source that these notes follow for terminology, the binary tree lemmas, array and linked representations, traversals, and the tree copy and equality procedures; it continues with threaded binary trees.
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms (3rd ed.), Appendix B.5 and Chapter 12: gives the mathematical definitions of trees (with 0-based height) and traversal in binary search trees.
- R. Sedgewick, Algorithms in C, Parts 1–4 (3rd ed.), Chapter 5: treats recursion and trees together; contains iterative versions of the traversals with a stack and a queue and proofs of tree properties.
- D. E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms (3rd ed.), Sections 2.3–2.3.2: gives binary tree traversal algorithms with a stack and examines in detail the representation of general trees by binary trees.
10.17References
- E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2nd ed., Chapter 5 (Trees).
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., MIT Press, Appendix B.5 and Chapter 12.
- R. Sedgewick, Algorithms in C, Parts 1–4, 3rd ed., Addison-Wesley, Chapter 5 (Trees).
- D. E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd ed., Addison-Wesley, 1997, Section 2.3.
Related pages: Chapter 10 slides · © Sercan Külcü. All rights reserved.