Introduction to Binary Trees - Advanced Topics in Java: Core Concepts in Data Structures - page 240

//node has no right subtree; search for the lowest ancestor of the
//node for which the node is in the ancestor's left subtree
//return null if there is no successor (node is the last in in-order)
TreeNode parent = node.parent;
while (parent != null && parent.right == node) {
node = parent;
parent = node.parent;
}
return parent;
} //end inOrderSuccessor

//The method findOrInsert from this Section goes here
} //end class BinaryTree

Program P8.3 reads words from the file words.in , builds the search tree, and performs an in-order traversal to
print the words in alphabetical order. For example, suppose words.in contains the following:

mac tee ode era ria lea vim

Program P8.3 builds the following binary search tree with parent pointers:

mac

era tee

lea ode vim

ria

It then prints this:

The in-order traversal is: era lea mac ode ria tee vim

8.9 Level-Order Traversal
In addition to pre-order, in-order, and post-order, another useful traversal is level-order . Here we traverse the tree level
by level, starting at the root. At each level, we traverse the nodes from left to right. For example, suppose we have the
following tree:

C

E G

N

B A

J

F

Its level-order traversal is C E G B A N F J .