236 BINARY TREES [CHAP. 10
Accordingly, in Fig. 10-1(a):(a) Bis a left successor andCis a right successor of the rootA.(b) The left subtree of the rootAconsists of the nodesB,D,E, andF, and the right subtree ofAconsists of the
nodesC,G, H, J, K, andL.(c) The nodesA, B, C,andHhave two successors, the nodesEandJhave only one successor, and the nodes
D, F, G, L, andKhave no successors, i.e., they are terminal nodes.Fig. 10-1Similar Binary Trees
Binary treesTandT′are said to besimilarif they have the same structure or, in other words, if they have the
same shape. The trees are said to becopiesif they are similar and if they have the same contents at corresponding
nodes.
EXAMPLE 10.1 Consider the four binary trees in Fig. 10-1(b). The three trees (1), (3), and (4) are similar. In
particular the trees (1) and (3) are copies since they also have the same data at corresponding nodes. The tree (2)
is neither similar nor a copy of the tree (4) because, in a binary tree, we distinguish between a left successor and
a right successor even when there is only one successor.
Terminology
Terminology describing family relationships is frequently used to describe relationships between the nodes
of a treeT. Specifically, supposeNis a node inTwith left successorS 1 and right successorS 2. ThenNis called
theparent(orfather)ofS 1 andS 2. Analogously,S 1 is called theleft child(orleft son)ofN, andS 2 is called the
right child(orright son)ofN. Furthermore,S 1 andS 2 are said to besiblings(orbrothers). Every nodeNin a
binary treeT, except the root, has a unique parent, called thepredecessorofN.
The terms descendant and ancestor have their usual meaning. That is, a nodeLis called adescendantof a
nodeN(andNis called anancestorofL) if there is a succession of children fromNtoL. In particular,Lis
called aleftorright descendantofNaccording to whetherLbelongs to the left or right subtree ofN.
Terminology from graph theory and horticulture are also used with a binary treeT. Specifically, the line
drawn from a nodeNofTto a successor is called anedge, and a sequence of consecutive edges is called apath.
A terminal node is called aleaf, and a path ending in a leaf is called abranch.
Each node in a binary treeTis assigned alevel number, as follows. The rootRof the treeTis assigned the
level number 0, and every other node is assigned a level number which is 1 more than the level number of its
parent. Furthermore, those nodes with the same level number are said to belong to the samegeneration.
Thedepth(orheight) of a treeT is the maximum number of nodes in a branch ofT. This turns out to be
1 more than the largest level number ofT. The treeTin Fig. 10-1(a) has depth 5.