TAOCP 2.3.4.5: Path Length

Section 2.3.4.5 exercises: 17/17 solved.

17 items

Section 2.3.4.5. Path Length

Exercises from TAOCP Volume 1 Section 2.3.4.5: 17/17 solved.

# Rating Category Status Time
1 [**] verified 1m22s
2 [**] verified 2m42s
3 [**] verified 2m
4 [**] solved 4m46s
5 [**] verified 2m33s
6 [**] verified 1m11s
7 [**] verified 4m09s
8 [**] verified 1m56s
9 [**] verified 57s
10 [**] verified 1m46s
11 [**] verified 46s
12 [**] verified 45s
13 [**] verified 3m39s
14 [**] verified 2m13s
15 [**] verified 1m54s
16 [**] verified 3m11s
17 [**] solved 3m30s
Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3.4.5: Path Length ›

TAOCP 2.3.4.5 Exercise 1

The internal path length of a binary tree is the sum of the depths of its $n$ internal nodes.
taocp mathematics algorithms volume-1 Jun 2, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3.4.5: Path Length ›

TAOCP 2.3.4.5 Exercise 2

**Solution to Exercise 2.
taocp mathematics algorithms volume-1 Jun 2, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3.4.5: Path Length ›

TAOCP 2.3.4.5 Exercise 3

We prove that a multiset of nonnegative integers $l_1,\dots,l_m$ occurs as the set of root-to-external-node path lengths in an extended binary tree if and only if \sum_{j=1}^m 2^{-l_j} = 1.
taocp mathematics algorithms volume-1 Jun 2, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3.4.5: Path Length ›

TAOCP 2.3.4.5 Exercise 4

The flaw in the previous solution is that it tries to prove lexicographic improvement after swapping two inorder blocks without controlling what the first differing entry actually is.
taocp mathematics algorithms volume-1 Jun 2, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3.4.5: Path Length ›

TAOCP 2.3.4.5 Exercise 5

The original solution fails because it treats the internal path length as if it were a simple additive marking that factors independently over subtrees.
taocp mathematics algorithms volume-1 Jun 2, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3.4.5: Path Length ›

TAOCP 2.3.4.5 Exercise 6

Let $n$ be the number of circular (internal) nodes and $s$ the number of square (external) nodes in an extended $t$-ary tree.
taocp mathematics algorithms volume-1 Jun 2, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3.4.5: Path Length ›

TAOCP 2.3.4.5 Exercise 7

**Solution.
taocp mathematics algorithms volume-1 Jun 2, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3.4.5: Path Length ›

TAOCP 2.3.4.5 Exercise 8

We prove Eq.
taocp mathematics algorithms volume-1 Jun 2, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3.4.5: Path Length ›

TAOCP 2.3.4.5 Exercise 9

Let $T$ be the extended binary tree in (11), and let each circular node $v$ be assigned the value equal to the sum of the weights $w_j$ of all external nodes in the subtree rooted at $v$.
taocp mathematics algorithms volume-1 Jun 2, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3.4.5: Path Length ›

TAOCP 2.3.4.5 Exercise 10

Let $w_1,\ldots,w_m\ge 0$.
taocp mathematics algorithms volume-1 Jun 2, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3.4.5: Path Length ›

TAOCP 2.3.4.5 Exercise 11

Yes.
taocp mathematics algorithms volume-1 Jun 2, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3.4.5: Path Length ›

TAOCP 2.3.4.5 Exercise 12

Let a binary tree have $n$ nodes and internal path length $I$.
taocp mathematics algorithms volume-1 Jun 2, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3.4.5: Path Length ›

TAOCP 2.3.4.5 Exercise 13

Let the external nodes be numbered $m,m+1,\ldots,2m-1$, and let the internal nodes be numbered $m-1,m-2,\ldots,1$, so that the last internal node created is node $1$, the root.
taocp mathematics algorithms volume-1 Jun 2, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3.4.5: Path Length ›

TAOCP 2.3.4.5 Exercise 14

Let a forest be a collection of extended binary trees, each node carrying a positive weight, and let the weight of a tree be the sum of weights of its leaves.
taocp mathematics algorithms volume-1 Jun 2, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3.4.5: Path Length ›

TAOCP 2.3.4.5 Exercise 15

We want to construct an extended binary tree minimizing M = \max_{i=1}^m (w_i + l_i), where $l_i$ is the depth of leaf $i$.
taocp mathematics algorithms volume-1 Jun 2, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3.4.5: Path Length ›

TAOCP 2.3.4.5 Exercise 16

**Corrected Solution for Exercise 2.
taocp mathematics algorithms volume-1 Jun 2, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3.4.5: Path Length ›

TAOCP 2.3.4.5 Exercise 17

Critical correction starts from the only valid backbone: part (a) and (b) already give a majorization principle, but the previous solution incorrectly tried to replace that with an assumed Huffman str...
taocp mathematics algorithms volume-1 Jun 2, 2026