Confusion with Threaded binary tree

Question

Hi all,

As per definition of Threaded binary tree given below

A binary tree is threaded by making all right child pointers that would normally be null point to the inorder successor of the node, and all left child pointers that would normally be null point to the inorder predecessor of the node.

But in above diagram right child pointers pointing to inorder predecessor and left child pointer pointing to inorder successor ,that making me confuse.

Answer 1

Both the quote and the graphic are correct, maybe you have your definition of successor and predecessor backward?

Answer 2

No, they are pointing to the correct node.

Answer 3

Look at C, what is it's predecessor? Successor? The order is

B then C then D

So B is C's predecessor, D is C successor.

Where does C's left pointer point? B, that's the predecessor, seems good to me.

Likewise, as expected, C's right pointer points to D.

Seems like statement, diagram and logic all agree. Where's the problem?

Answer 4

In some books, when the authors refer to the 'left child' they mean the child which appears to the right of the parent node, (presumably because it is to the left from the node's own point of view). The same applies the other way around - they refer to right as left

Be careful not to get confused!

In the diagram above, the definition is correct: the left child is referred as to as the left child.

The case of the right node is similar

Answer 5

The definition and the graphic are consistent with each other. However, the following statement is false:

But in above diagram right child pointers pointing to inorder predecessor and left child pointer pointing to inorder successor