Registered: 13 years ago
I am really struggling with this question. Did any of you manage to get the same BST for both given traversals. I've done it a few dozen times now and come up with the same solution- meaning different BST's for each traversal. I've even tried to simulate the BST's in Mathematica but thats no help. Any ideas or suggestions?
Registered: 14 years ago
Think of it logically, in a Pre-order traversal, the first node visited is the root and the last visited is the right-most leaf. Thus the root in this case is A. And M is a leaf on the right-hand branch from the root.
In an in-order traversal, the left branch is visited first, then the node itself then the right branch is visited. Knowing that A is the root, you can divide the in-order print out into the left branch and right branch with A in the middle. You can also tell that because it keeps going left, left, left, left, etc. until it reaches a NULL, you know that the first node printed out is the left-most node and the last node printed out is the right-most node.
From all of this you should have: A is the root, C is the left-most node and it may or may not have a right branch but does not have a left branch, and that L is the right-most node but M is the right-most leaf. Thus M is the left branch of L and L doesn't have a right branch.
You can break the tree up into smaller sections (ie. left of root, and right of root) and follow this same logic until you have the complete structure.
The easiest way is to iterate:
PO : ABCDEFGHIJKLM
IN : CEDFBAHJIKGML
The first node is the root in the PO list. The IO list show the left/right split.
PO : A | BCDEF | GHIJKL
IN : CEDFB | A | HJIKGML
Now just take one branch and do the same thing again.
PO : BCDEF
IN : CEDFB
The first node in PO is the root. The IO shows the layout of the left/right split.
PO : B | CDEF |
IO : CEDF | B |
This shows that there is not right branch to B.
You keep breaking it up until you've used up all the nodes in the left branch and the you start on the right branch