Given that the postorder traversal sequence of a binary tree is DABEC and the inorder traversal sequence is DEBAC, what is its preorder traversal sequence?
Given that the postorder traversal sequence of a binary tree is DABEC and the inorder traversal sequence is DEBAC, what is its preorder traversal sequence?
----C
---/
--E
-/-\
D---B
-----\
------A
I know the answer looks like this.... But I want to ask... Why is it drawn this way??
Postorder traversal means: left-right-root, and inorder traversal means: left-root-right.
- From postorder traversal, we know C is the root node.
- From inorder traversal, we see that C has no right subtree. From postorder, the next root node before C is E.
- From inorder sequence DEBA, D must be in the left subtree of E. From postorder sequence DAB, B is the next root node after D and A, so B must be the right child of E. From inorder sequence BA, A must be the right child of B.