TAOCP 2.3 Exercise 8
A binary tree is not necessarily a tree in the sense of graph theory.
Exercise 8. ▶ [**] [03] What binary tree is not a tree?
Verified: no
Solve time: 37s
A binary tree is not necessarily a tree in the sense of graph theory. By definition, a binary tree permits empty subtrees. Hence the binary tree consisting only of the empty tree contains no nodes at all.
A tree is a connected graph. Since the empty binary tree has no nodes and therefore is not a connected graph, it is a binary tree that is not a tree. Thus the answer is
$\boxed{\text{the empty binary tree}.}$