How to find the predecessor and successor of the node in the traversal sequence of a threaded binary

How to find the predecessor and successor of the node in the
traversal sequence of a threaded binary tree?

Using the in-order threaded binary tree in →Fig. 1.70
as an example, the right links of all the leaf nodes in the tree serve as the
thread, and therefore the RightChild field of the leaf node points to the
successor node of the node. For example, the successor of node C in →Fig.
1.70 is node A, and the successor of node F is node E.

When an internal node has its right thread tag as 0, we know
its RightChild pointer points to its right child; therefore, we would not be
able to obtain the successor node from RightChild. An example is node D.

However, we know from the definition of in-order traversal
that the successor of node D, node F, should be the first node to be visited
when traversing the right subtree of D, that is, the most bottom-left node of
the right subtree of D.

Similarly, the pattern when finding the predecessor node in
an in-order threaded tree is: If the node’s left tag is marked as 1, then
LeftChild stores the thread which directly points to its predecessor node.
Otherwise, the node last visited when traversing the left subtree, that is, the
most bottom-right node of the left subtree, is its predecessor node. The
predecessor and successor of each node in →Fig. 1.70 are given in
→Table 1.12.

Table 1.12:

The predecessor and successor in sequence obtained via
inorder traversal.

The marker for right thread is 1: the right child is the
successor.

The marker for right thread is 0: the leftmost node in the
right subtree is the successor.

The leftmost child of the right subtree: the first node to
be visited when we in-order traverse the right subtree.

The marker for left thread is 1: the left child is the
predecessor.

The marker for left thread is 0: the rightmost node in the
left subtree is the predecessor.

The rightmost child of the left subtree: the last node to be
visited when we in-order traverse the left subtree.

From this we can see that if the height of the threaded
binary tree is h, then in the worst-case scenario, we can find the predecessor
or successor node of a node in O(h) time. When we traverse an in-order threaded
binary tree, there is no need to store the information of the subtree to be
visited with recursion/stacks, like when we traverse nonthreaded trees.

The method to obtain in-order traversal sequence from
inorder traversal threaded binary tree:

Visit the root node

Find the predecessor sequence of the root

Find the successor sequence of the root

The method to obtain pre-order traversal sequence from
preorder traversal threaded binary tree:

Visit the root node

Find the successor sequence of the root

The method to obtain post-order traversal sequence from
post-order traversal threaded binary tree: