How can I construct a threaded binary tree with post-order threads?

Question

Threaded binary tree with post-order threads

I want to construct a threaded binary tree consisting of nine nodes A, B, C, D, E, F, G, H, and I with post-order threads. Each node has five fields, which are LeftThread (true or false), LeftChild (pointer to a node), data (of char type), RightChild(pointer to a node), and RightThread (true or false). This is how the binary tree (with only the data of the nodes showing) looks like:

 A
 / \
 B C
 / \ / \
 D E F G
 / \
H I

I have two main doubts, which are:

1. Is B the left child of F, even though they have different parent nodes?
2. Where does the right child of G point to? Does it point to the root, or does it point back to node C?

Please note that the image only reflects my attempt at solving the problem and might be incorrect.

Answer 1

Your post-order sequence seems correct. From this you can read the answer to your questions.

B is the post-order predecessor of F. Hence B is the left thread of F (as F originally does not have a left child).

Similarly for G. Its post-order successor is C, and that is where its right thread will point to.

• benhpark: Thank you so much!