i only know that N is the root of the tree but there is duplicate N in this case
for example POSTORDER traversal: Y, H, E, A, N , H, O, I, T, P, N
INORDER traversal: H, Y, P, H, E, N, A, T, I, O, N
1
-
4$\begingroup$ This question needs more context. We do not know which book you have in front of you. $\endgroup$– reinierpostCommented Jul 31 at 9:51
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
The content of the nodes has nothing to do with the tree structure. Just replace the letters by hex digits $0_h\to A_h$
$\begingroup$
$\endgroup$
Trial and error, I suppose. Note there is also a duplicate H.
For a binary tree with root R and subtrees A and B, we obtain the postorder as post(A) post (B) R, and the inorder as in(A) R in(B). The sequences post(A) and in(A) are permutations of the same letters.
You can indeed infer that N is in the root of the tree because it is last in the postorder. But is it the first or second N in the inorder? If it is the first N, the subtrees would contain (H, Y, P, H, E) and (A, T, I, O, N). That would imply that the postorder also starts with a permutation of (H, Y, P, H, E) and then a permutation of (A, T, I, O, N). This is not possible, the letter P is too much at the end.
Etcetera.
