Binary Trees - Building Java Programs: A Back to Basics Approach - page 1004

Binary Search Tree
A binary tree in which every node has the binary search tree property.

Here is a binary search tree of names:

Lisa

Bart Marge

Homer Maggie Smithers

Flanders Krusty Milhouse

The names appear in the tree using alphabetical ordering (also known as
lexicographic ordering ). For example, the overall root stores "Lisa" , which means
that all of the names in the left subtree are alphabetically less than or equal to "Lisa"
and all names in the right subtree are alphabetically greater than "Lisa" .
Consider the result you obtain when you perform an inorder traversal of the tree:

Bart, Flanders, Homer, Krusty, Lisa, Maggie, Marge, Milhouse, Smithers

This list of names is in alphabetical order. This result isn't terribly surprising when
you think about the binary search tree property. In a binary search tree, you know that
values which are alphabetically less than or equal to the root appear in the left subtree
and that values which are alphabetically greater appear in the right subtree. For any
given subtree, an inorder traversal traverses the left subtree first, then the root, then
the right subtree, which means you visit the nodes in this order:

(values <= root data) root data (values > root data)

1st 2nd 3rd

Therefore, the root value is printed at just the right point in time (after the values
that are alphabetically less than or equal to it and before the values that are alpha-
betically greater than it). And because every node in the tree has the binary search
tree property, you know that the value stored in each node is printed in the correct
position relative to the values that appear below it in the tree. The overall result is