1
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you so much! $\endgroup$ Commented Oct 22, 2024 at 7:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.