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

With parent fields, we can do traversals without recursion and the stacking/unstacking of arguments and local
variables implied by it. For example, we can perform an in-order traversal as follows:

get the first node in in-order; call it “node”
while (node is not null) {
visit node
get next node in in-order
}

Given the non-null root of a tree, we can find the first node in in-order with this:

TreeNode node = root;
while (node.left != null) node = node.left;

We go as far left as possible. When we can't go any further, we have reached the first node in in-order. After the
code is executed, node will point to the first node in in-order.
The main problem to solve is the following: given a pointer to any node, return a pointer to its in-order successor ,
that is, the node that comes after it in in-order, if any. The last node in in-order will have no successor.
There are two cases to consider:

1. If the node has a nonempty right subtree, then its in-order successor is the first node in

the in-order traversal of that right subtree. We can find it with the following code, which
returns a pointer to the in-order successor:

if (node.right != null) {
node = node.right;
while (node.left != null) node = node.left;
return node;
}

For example, consider the following tree:

C

G

E

N

B A

F

J K

H

The in-order successor of G is found by going right once (to N ) and then as far left as possible (to J ). J is the in-
order successor of G .

2. If the node has an empty right subtree, then its in-order successor is one of its ancestors.

Which one? It's the lowest ancestor for which the given node is in its left subtree. For
example, what is the in-order successor of B ?
We look at B's parent, E. Since B is in the right subtree of E, it is not E.

We then look at E's parent, C. Since E (and hence, B) is in the left subtree of C, we conclude
that C is the in-order successor of B.
Note, however, that K, being the last node in in-order, has no successor. If we follow parent
pointers from K, we never find one with K in its left subtree. In this case, our function will
return null.