TAOCP 2.3.1: Traversing Binary Trees
Section 2.3.1 exercises: 37/37 solved.
Section 2.3.1. Traversing Binary Trees
Exercises from TAOCP Volume 1 Section 2.3.1: 37/37 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [01] | simple | solved | 30s |
| 2 | [11] | simple | solved | 38s |
| 3 | [20] | medium | solved | 43s |
| 4 | [20] | medium | solved | 32s |
| 5 | [22] | medium | solved | 35s |
| 6 | [M22] | math-medium | solved | 37s |
| 7 | [22] | medium | solved | 27s |
| 8 | [20] | medium | solved | 32s |
| 9 | [M20] | math-medium | solved | 38s |
| 10 | [20] | medium | solved | 40s |
| 11 | [HM41] | hm-project | solved | 49s |
| 12 | [22] | medium | solved | 37s |
| 13 | [24] | medium | solved | 48s |
| 14 | [20] | medium | solved | 27s |
| 15 | [15] | simple | solved | 41s |
| 16 | [22] | medium | solved | 27s |
| 17 | [22] | medium | solved | 36s |
| 18 | [24] | medium | solved | 53s |
| 19 | [27] | hard | verified | 1m41s |
| 20 | [23] | medium | solved | 33s |
| 21 | [33] | hard | solved | 32s |
| 22 | [25] | medium | solved | 36s |
| 23 | [22] | medium | solved | 49s |
| 24 | [M20] | math-medium | solved | 46s |
| 25 | [M24] | math-medium | solved | 52s |
| 26 | [M24] | math-medium | solved | 59s |
| 27 | [28] | hard | verified | 3m02s |
| 28 | [00] | immediate | solved | 47s |
| 29 | [M25] | math-medium | solved | 53s |
| 30 | [22] | medium | verified | 1m13s |
| 31 | [23] | medium | solved | 56s |
| 32 | [21] | medium | verified | 57s |
| 33 | [30] | hard | solved | 37s |
| 34 | [22] | medium | solved | 45s |
| 35 | [40] | project | solved | 47s |
| 36 | [M23] | math-medium | solved | 39s |
| 37 | [24] | medium | verified | 2m40s |
TAOCP 2.3.1 Exercise 1
In tree (2), the root is $A$, so $RLINK(T)$ points to $C$.
TAOCP 2.3.1 Exercise 2
Let `T` denote the root of the binary tree in the figure.
TAOCP 2.3.1 Exercise 3
The statement claims that "The terminal nodes of a binary tree occur in the same relative position in preorder, inorder, and postorder.
TAOCP 2.3.1 Exercise 4
Let us define the new traversal order recursively, as in the exercise: 1.
TAOCP 2.3.1 Exercise 5
Let the representation of a node be the binary string $\alpha$, where the root is represented by `"1"`, the left child of $\alpha$ is $\alpha0$, and the right child is $\alpha1$.
TAOCP 2.3.1 Exercise 6
Let a binary tree have $n$ nodes, with preorder sequence u_1 u_2 \dots u_n and inorder sequence
TAOCP 2.3.1 Exercise 7
Let the preorder of the binary tree be $u_1 u_2 \dots u_n$ and the inorder be $v_1 v_2 \dots v_n$.
TAOCP 2.3.1 Exercise 8
Let the nodes of a binary tree be distinct.
TAOCP 2.3.1 Exercise 9
Let a binary tree with `n` nodes be traversed using Algorithm `T`.
TAOCP 2.3.1 Exercise 10
The stack grows only in step `T3`, where the current value of `P` is pushed onto `A` and then `P` is replaced by `LLINK(P)`.
TAOCP 2.3.1 Exercise 11
Let $H_n$ denote the largest number of entries simultaneously present in stack $A$ during the execution of Algorithm $T$ on a binary tree with $n$ nodes.
TAOCP 2.3.1 Exercise 12
We aim to construct an algorithm analogous to Algorithm `T` that traverses a binary tree in _preorder_, visiting each node exactly once, and then prove its correctness by induction on the number of no...
TAOCP 2.3.1 Exercise 13
A postorder traversal must process a node only after both of its subtrees have been traversed.
TAOCP 2.3.1 Exercise 14
In the representation (2), each node contains exactly two links, `LLINK` and `RLINK`.
TAOCP 2.3.1 Exercise 15
Let a node $P$ of a threaded binary tree be given.
TAOCP 2.3.1 Exercise 16
Let `P` point to a node of a binary tree, and consider `Q = P*`, the successor of `NODE(P)` in preorder.
TAOCP 2.3.1 Exercise 17
We are asked to give an algorithm analogous to Algorithm `S` that determines the preorder successor `P*` of a node `P` in a threaded binary tree with a list head as in `(8), (9), (10)`.
TAOCP 2.3.1 Exercise 18
The double-order traversal visits each node twice.
TAOCP 2.3.1 Exercise 19
Exercise 19 asks for an algorithm analogous to Algorithm `S`, but for the calculation of the preorder successor.
TAOCP 2.3.1 Exercise 20
Algorithm `T` uses an auxiliary stack `A` in consecutive memory locations.
TAOCP 2.3.1 Exercise 21
Let `T` be a pointer to a binary tree of $n$ nodes with the conventional representation `(2)`, that is, each node `P` has two link fields `LLINK(P)` and `RLINK(P)` pointing either to the left or right...
TAOCP 2.3.1 Exercise 22
We are asked to write a MIX program that implements the algorithm of Exercise 21, which traverses an unthreaded binary tree in inorder _without using any auxiliary stack_, modifying the `LLINK` and `R...
TAOCP 2.3.1 Exercise 23
A _right-threaded_ binary tree contains ordinary left links and either ordinary right links or right threads.
TAOCP 2.3.1 Exercise 24
No.
TAOCP 2.3.1 Exercise 25
We first interpret the definition of $\preceq$ as a recursive lexicographic comparison of trees: the empty tree precedes every tree; among nonempty trees, the roots are compared first; if the roots ag...
TAOCP 2.3.1 Exercise 26
Let $D(T)$ denote the double-order sequence of a binary tree $T$, as defined in exercise 18.
TAOCP 2.3.1 Exercise 27
Exercise 25 defines a linear ordering on binary trees recursively.
TAOCP 2.3.1 Exercise 28
Algorithm `C` constructs a new tree by creating a new node corresponding to each node of the original tree, copying the information field, and preserving the left and right subtree relationships.
TAOCP 2.3.1 Exercise 29
Algorithm `C` is intended to construct a new binary tree whose nodes contain the same information as the original tree and whose link structure is identical, regardless of whether a field represents a...
TAOCP 2.3.1 Exercise 30
Let `T` be an unthreaded binary tree, represented in the standard form of (2), and let `P` be a pointer to a node of `T`.
TAOCP 2.3.1 Exercise 31
Let `T` be the pointer to the right-threaded binary tree, and let `AVAIL` be the head of the list of available nodes.
TAOCP 2.3.1 Exercise 32
Exercise 31 refers to Algorithm `I` for insertion into a right-threaded binary tree.
TAOCP 2.3.1 Exercise 33
Let $T$ be a binary tree represented in memory with nodes containing three fields: `LTAG(P), LLINK(P), RLINK(P)`.
TAOCP 2.3.1 Exercise 34
Let the right-threaded binary trees use the conventions of the section: - `LLINK(P)` is either a left child or `\Lambda`.
TAOCP 2.3.1 Exercise 35
A _ternary tree_ is defined recursively as either empty, or consisting of a root together with three ordered ternary subtrees, called the first, second, and third subtrees.