The top of the tree (the node tree refers to) is called the root. In keeping with the tree metaphor, the other nodes are called branches and the nodes at the tips with null references are called leaves. It may seem odd that we draw the picture with the root at the top and the leaves at the bottom, but that is not the strangest thing.
To make things worse, computer scientists mix in another metaphor—the family tree. The top node is sometimes called a parent and the nodes it refers to are its children. Nodes with the same parent are called siblings.
• the empty tree, represented by None, or
• a node that contains an object reference and two tree references.
20.1 Building trees
self.left = left
self.right = right
One way to build a tree is from the bottom up. Allocate the child nodes first:
left = Tree(2)
>>> tree = Tree(1, Tree(2), Tree(3))
Either way, the result is the tree at the beginning of the chapter.