TAOCP 2.3: Trees

Section 2.3 exercises: 22/22 solved.

22 items

Section 2.3. Trees

Exercises from TAOCP Volume 1 Section 2.3: 22/22 solved.

#	Rating	Status	Time
1	[**]	solved	31s
2	[**]	solved	29s
3	[**]	solved	29s
4	[**]	solved	35s
5	[**]	solved	31s
6	▶ [**]	solved	36s
7	[**]	solved	33s
8	▶ [**]	solved	37s
9	[**]	solved	34s
10	[**]	solved	32s
11	▶ [**]	solved	27s
12	[**]	solved	32s
13	[**]	solved	32s
14	[**]	solved	45s
15	▶ [**]	verified	36s
16	[**]	solved	35s
17	[**]	solved	33s
18	[**]	solved	26s
19	[**]	solved	35s
20	▶ [**]	solved	28s
21	[**]	solved	38s
22	▶ [**]	solved	27s

Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3: Trees ›

TAOCP 2.3 Exercise 1

There are three nodes labeled $A$, $B$, and $C$.

Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3: Trees ›

TAOCP 2.3 Exercise 2

With three nodes $A$, $B$, and $C$, every tree has exactly two edges.

Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3: Trees ›

TAOCP 2.3 Exercise 3

We proceed by induction on the number of nodes in the tree.

Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3: Trees ›

TAOCP 2.3 Exercise 4

False.

Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3: Trees ›

TAOCP 2.3 Exercise 5

By definition, the _degree_ of a node is the number of its children.

Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3: Trees ›

TAOCP 2.3 Exercise 6

Two nodes `X` and `Y` of a tree are said to be _$m$th cousins, $n$ times removed_ if the following holds.

Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3: Trees ›

TAOCP 2.3 Exercise 7

Let $A$ be the nearest common ancestor of $X$ and $Y$.

Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3: Trees ›

TAOCP 2.3 Exercise 8

A binary tree is not necessarily a tree in the sense of graph theory.

Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3: Trees ›

TAOCP 2.3 Exercise 9

In both binary trees of (1), the root is `A`.

Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3: Trees ›

TAOCP 2.3 Exercise 10

Not every collection of nested sets corresponds to a tree in the sense defined in Section 2.

Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3: Trees ›

TAOCP 2.3 Exercise 11

The concepts of level, degree, parent, and child extend naturally to infinite trees defined as collections of nested sets.

Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3: Trees ›

A partially ordered set $(P, \preceq)$ corresponds to an unordered tree if and only if $P$ has a least element $r$ (the root) and, for every $x \in P \setminus {r}$, the set of elements less than $x$...

Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3: Trees ›

TAOCP 2.3 Exercise 13

The path from node $X$ to the root consists of all nodes that are ancestors of $X$, including $X$ itself and the root.

Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3: Trees ›

TAOCP 2.3 Exercise 14

Let the elements of $S$ be regarded as nodes, and define the parent of a node $\alpha.m$ to be $\alpha$ when $m=1$, and define the nodes $\alpha.1,\alpha.2,\ldots$ to be the children of $\alpha$ whene...

Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3: Trees ›

TAOCP 2.3 Exercise 15

A natural notation for nodes of a binary tree extends the Dewey decimal system by encoding each branching choice as a binary digit.

Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3: Trees ›

TAOCP 2.3 Exercise 16

For the expression $2(a - b/c)$, the corresponding tree has the multiplication $2 \cdot (\cdot)$ at the root.

Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3: Trees ›

TAOCP 2.3 Exercise 17

The node `Z[1,2,2]` is the second child of the second child of the first tree in the forest `Z`.

Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3: Trees ›

TAOCP 2.3 Exercise 18

In List (3), the notation `L[i_1, i_2, \dots]` refers to the node reached by starting at the root of `L`, following the $i_1$-th child, then the $i_2$-th child of that node, and so on.

Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3: Trees ›

TAOCP 2.3 Exercise 19

The List $L = (a,(L))$ consists of two elements: the first element is the atom $a$, and the second element is a List identical to $L$ itself.

Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3: Trees ›

TAOCP 2.3 Exercise 20

Let $I(T)$ denote the number of internal nodes, namely nodes having two children, and let $L(T)$ denote the number of leaves.

Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3: Trees ›

TAOCP 2.3 Exercise 21

Let $N$ be the total number of nodes and let $t$ be the number of terminal nodes.

Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3: Trees ›

TAOCP 2.3 Exercise 22

We represent binary trees graphically using standard European paper sizes `A0`, `A1`, `A2`, .

TAOCP 2.3: Trees

Section 2.3. Trees

TAOCP 2.3 Exercise 1

TAOCP 2.3 Exercise 2

TAOCP 2.3 Exercise 3

TAOCP 2.3 Exercise 4

TAOCP 2.3 Exercise 5

TAOCP 2.3 Exercise 6

TAOCP 2.3 Exercise 7

TAOCP 2.3 Exercise 8

TAOCP 2.3 Exercise 9

TAOCP 2.3 Exercise 10

TAOCP 2.3 Exercise 11

TAOCP 2.3 Exercise 12

TAOCP 2.3 Exercise 13

TAOCP 2.3 Exercise 14

TAOCP 2.3 Exercise 15

TAOCP 2.3 Exercise 16

TAOCP 2.3 Exercise 17

TAOCP 2.3 Exercise 18

TAOCP 2.3 Exercise 19

TAOCP 2.3 Exercise 20

TAOCP 2.3 Exercise 21

TAOCP 2.3 Exercise 22