TAOCP 2.3.1 Exercise 1

In tree (2), the root is $A$, so $RLINK(T)$ points to $C$.

taocpmathematicsalgorithmsvolume-1simple

Section 2.3.1: Traversing Binary Trees

Exercise 1. [01] In the binary tree (2), let INFO(P) denote the letter stored in NODE(P). What is INFO(LLINK(RLINK(RLINK(T))))?

Verified: no
Solve time: 30s

In tree (2), the root is $A$, so $RLINK(T)$ points to $C$. The right child of $C$ is $F$, hence $RLINK(RLINK(T))$ points to $F$. The left child of $F$ is $H$, so

$$ LLINK(RLINK(RLINK(T))) $$

points to the node containing $H$.

Therefore,

$$ \boxed{\mathrm{INFO}(LLINK(RLINK(RLINK(T)))) = H}. $$