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:
Visit the root node
Find the predecessor sequence of the root