TAOCP 2.3.1 Exercise 9

Let a binary tree with `n` nodes be traversed using Algorithm `T`.

taocpmathematicsalgorithmsvolume-1math-medium

Section 2.3.1: Traversing Binary Trees

Exercise 9. [M20] When a binary tree having n nodes is traversed using Algorithm T, state how many times each of steps T1, T2, T3, T4, and T5 is performed (as a function of n).

Verified: no
Solve time: 38s

Solution

Let a binary tree with n nodes be traversed using Algorithm T. We determine the number of times each step T1 through T5 is executed as a function of n. Denote by L the set of links (pointers) in the tree, so |L| = 2n in the conventional representation (each node has LLINK and RLINK).

Step T1 [Initialize.] This step sets A empty and P <- T. It is executed once per traversal, independent of n. Thus, T1 is executed exactly once.

Step T2 [P = Λ?] Step T2 is tested each time before pushing a nonempty subtree on the stack or before returning from the stack. Let us analyze systematically. Each nonempty node P will eventually have P <- LLINK(P) in step T3 (or P <- RLINK(P) in step T5). Every null link causes step T2 to detect P = Λ and branch accordingly.

Each node has two links. Step T2 is tested for the left link (via step T3) and for the right link (via step T5). Each null link is tested once. Since there are n nodes, there are n + 1 null links in a binary tree (by standard property of binary trees; each tree with n nodes has n + 1 external nodes). Additionally, each nonempty node is tested when P points to it. Therefore, step T2 is executed exactly once for each left and right visit, plus once for the initial P <- T. More formally, step T2 is executed 2n + 1 times.

Step T3 [Stack ← P.] Step T3 executes when P ≠ Λ in step T2. Each nonempty node P is pushed exactly once onto the stack when first encountered. Therefore, step T3 is executed exactly n times.

Step T4 [P ← Stack.] Step T4 is executed each time after traversal of a left subtree when the stack is not empty. Each node that was pushed onto the stack in T3 will cause a corresponding execution of T4 when the left subtree has been traversed. Since T3 is executed n times, step T4 is executed exactly n + 1 times, accounting for the final check when the stack becomes empty.

Step T5 [Visit P.] Step T5 visits the node and advances to the right subtree. Each nonempty node is visited exactly once. Therefore, step T5 is executed exactly n times.

We can summarize:

  • T1 is executed 1 time.
  • T2 is executed 2n + 1 times.
  • T3 is executed n times.
  • T4 is executed n + 1 times.
  • T5 is executed n times.

These counts can be verified inductively. For the empty tree (n = 0), step T1 executes once, T2 executes once, and steps T3, T4, T5 do not execute, which agrees with the formulas. Assume the counts hold for all trees with fewer than n nodes. For a tree of size n, the root executes T3 once, T5 once, T2 twice for its two links (left and right), and T4 once after the left subtree, in addition to the counts accumulated from the left and right subtrees. Summing these counts yields exactly the formulas above. This completes the induction.

\boxed{ \text{T1: } 1, \quad \text{T2: } 2n+1, \quad \text{T3: } n, \quad \text{T4: } n+1, \quad \text{T5: } n } ] ∎